1.桶排序

之前接触的排序，快排，堆排，归并的时间复杂度O(NlgN)，冒泡时间复杂度O(N^2)。而桶排序是时间复杂度O(N)的排序，带有哈希的思想

桶排序是指，对于一个数组nums

• 1. 求出nums的值域Y
• 2. 分桶。将nums的值域Y划分成m份，一般而言是相等的m份 - m个桶
• 3. 哈希入桶。遍历nums，将每个元素映射到对应的桶内。一个桶可以含有多个元素，也可以作为空桶存在
• 4. 桶内排序。桶与桶之间是有序的，桶内的元素是无序的，根据实际选择适当的排序算法对桶内元素进行排序后，得到最终整体有序的解

时间复杂度分析：
假如桶的个数是 m，则每个桶中的数据量平均 n/m, 桶内元素使用快排排序，则桶排序的时间复杂度 m(n/m)(log(n/m)) = n log(n/m)。只要我们总是令桶的数量m趋近于n，则log(n/m)可以认为是一个常数，因此桶排序的时间复杂度O(n)

空间复杂度分析：
所有元素都需要映射重新放到桶内，O(n)

2.例题

leetcode 164. 最大间距
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。

示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3

无脑思路：排序+遍历，复杂度O(nlgn)
题目要求O(n)，则不能严格硬排序。但求相邻元素最大差，前提必须有序
借助【桶排序】思想，要O(N)时间复杂度，则映射所有元素到对应的【n个容量相同的桶，每个桶的容量是（max-min）/ len(nums)】中。要么每个桶都恰好有一个数，要么一些桶空着另一些桶存放了多个数。我们把每个桶的最小值和上一桶的最大值做差，取最大差即为所求

class Solution:
    def maximumGap(self, nums: List[int]) -> int:
        l = len(nums)
        if l < 2: return 0

        ma, mi = float('-inf'), float('inf')
        # 查找最大最小值，确定nums值域
        for ele in nums:
            ma = max(ma, ele)
            mi = min(mi, ele)
        # 用dict记录元素的分桶情况，初始化dict-bucket
        bucket = dict()
        for i in range(l+1):
            bucket[i] = []
        # 求桶容量
        bucket_size = (ma-mi) / l
        if bucket_size == 0:
            return 0
         # 开始分桶
        for ele in nums:
            offset = ele - mi
            key = int(offset // bucket_size)
            bucket[key].append(ele)
        # 求res
        res = float('-inf')
        pre_index = 0
        for i in range(1,l+1):
            # 跳过空桶
            if not bucket[i]:
                continue
            res = max(min(bucket[i]) - max(bucket[pre_index]), res)
            pre_index = i
        return res

3. 计数排序

本质上，计数排序是一种特殊的桶排序，对于一个上下界为a, b的待排序nums，值域内的每个值都对应一个桶，共有(b-a+1)个桶。一般的桶排序可以多个不同的值放入一个桶

典型的应用场景就是：高考分数排名。高考成绩满分 750 分，最低分0分，就设置 751 个桶，对应 0，1，...750 的分数，只需要将百万考生按成绩放在每个桶中，再依次从每个桶中输出学生成绩，就完成了排序

计数排序的实现python版：

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        res = []
        if not nums:
            return res

        ma = max(nums)
        mi = min(nums)
        l = ma - mi + 1
        # bucket用数组表示，bucket[i]的值表示桶内元素出现的次数
        bucket = [0 for i in range(l)]
        # 哈希入桶
        for ele in nums:
            index = ele - mi
            bucket[index] += 1
       
        for i in range(len(bucket)):
            count = bucket[i]
            val = i + mi
            for j in range(count):
                res.append(val)
        return res