线性时间排序

计数 排序 核心是将输入的数据值转化为键存储在额外开辟的数组空间中，其基本思想一是：在排序之前，先统计遍历源数组，得到最大值 max 和最小值 min，然后开辟一个长度为 max-min+1 的计数数组，计数数组中 index 的元素记录的值是原数组中某元素出现的次数，遍历原数组进行计数，最后按顺序输出计数数组中不为0的元素，如果出现多次，则输出多次。

例如要排序的数组为 [5, 3, 4, 7, 2, 4, 3, 4, 7]，最大值为 7，最小值为 2，所以计数数组的长度为 6，然后按照下图的方式，记录每个数出现的次数，最后遍历计数数组进行输出。

具体可参考 五分钟学算法 公众号的文章： 【图解数据结构】 一组动画彻底理解计数排序

Python 实现

def counting_sort(nums):
    max_num = max(nums)
    min_num = min(nums)
    length = max_num - min_num + 1
    src = [0 for _ in range(length)]  # 计数数组

    for i in nums:  # 计数
        tmp = i - min_num
        src[tmp] += 1

    res = []
    for j in range(len(src)):  # 输出
        while src[j]:
            src[j] -= 1
            res.append(j + min_num)

    return res

计数排序是一种非常快捷的稳定排序方法，时间复杂度和空间复杂度均为 O(n+k) ，其中 n 为要排序的数的个数，k 为要排序的数组的最大值。

计数排序的是消耗空间复杂度来优化时间复杂度的排序方法，对一定量的整数排序时候的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

时间复杂度

• 平均时间复杂度：O(n+k)。
• 最优时间复杂度：O(n+k)。
• 最坏时间复杂度：O(n+k)。
• 空间复杂度：O(k)。
• 稳定性：稳定。

桶排序

基本思路

桶排序是一种基于计数的排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再分别排序（有可能再使用别的 排序算法 或是以递归方式继续使用桶排序进行排序）。

简单来说就是设置 n 个数组当作空桶子。遍历数组，并且把项目一个一个放到对应的桶子去。对每个不是空的桶子进行排序。从不是空的桶子里把项目再放回原来的数组中。

具体可参考 五分钟学算法 公众号的文章： 【图解数据结构】 一组动画彻底理解桶排序

Python 实现

def bucket_sort(nums, n):
    bucket = [[] for _ in range(n)]

    max_num = max(nums)
    min_num = min(nums)
    gap = (max_num - min_num + 1) // 5  # 确定每个桶的范围

    for i in nums:  # 放进桶中
        index = i // (gap + min_num)
        bucket[index].append(i)

    for i in range(n):  # 桶内排序
        bucket[i].sort()

    index = 0
    for i in range(n):  # 输出
        for j in range(len(bucket[i])):
            nums[index] = bucket[i][j]
            index += 1
    return nums

时间复杂度

• 平均时间复杂度：O(n+k)。
• 最优时间复杂度：O(n+k)。
• 最坏时间复杂度：O(n**2)。
• 空间复杂度：O(n+k)。
• 稳定性：稳定。

基数排序

基本思路

基数排序是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。通过将要比较的位（个位、十位、百位…），将要排序的元素分配至 0~9 个桶中，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，得到的数组就是有序的。

具体可参考 五分钟学算法 公众号的文章： 【图解数据结构】 一组动画彻底理解基数排序

Python 实现

def RadixSort(nums):
    n = 1
    max_num = max(nums)
    while max_num > 10 ** n:  # 得到最大数是几位数
        n += 1

    i = 0  # 从个位开始
    while i < n:
        bucket = [[] for _ in range(10)]  # 初始化桶

        for x in nums:  # 对每一位进行排序
            radix = int((x / (10 ** i)) % 10)  # 得到每位的基数
            bucket[radix].append(x)  # 加入对应基数的桶中

        j = 0
        for k in range(10):
            if len(bucket[k]) != 0:  # 若桶不为空
                for y in bucket[k]:  # 将该桶中每个元素
                    nums[j] = y  # 放回到数组中
                    j += 1
        i += 1
    return nums