排序算法——计数排序

概述

计数排序是一个非基于比较的[序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为\(Ο(n+k)\)（其中k是整数的范围），快于任何比较排序算法。

但是，计数排序算法的快速是使用空间来换取的。当整数范围过大时，其效率甚至不如复杂度为\(O(nlog(n))\)的比较排序类算法。

计数排序适用于对整数进行排序，首先建立一个数组，初始值为0.数组的尺寸为需要排序元素的最大最小值之差减一，定义映射关系(通常减去排序元素中的最小值即可)，将原来元素映射到数组中。元素映射后的值便对应数组的索引。遍历元素，将元素所对应数组处的值加1，最后依次取出数组中的值完成排序。

其实这就是桶排序的时间最优的特殊情况。

---

实现

此处沿用桶排序的特例。所有元素的值都在50~59之间，因此可以使用\(a-50\)这样一个映射关系将所有元素映射至数组的索引0~9。遍历元素依次给相应的位置上的数组元素加一。

遍历结束后每个计数数组中的元素数量：

image-20210418215621271

将上面的例子排序后输出：

def Sort(nums):
    buckets = [0] * 10  # 建立固定长度数组
    for i in nums:
        buckets[i - 50] += 1   # 索引计算

    for i in range(len(buckets)):  # 输出排序后的值
        while buckets[i] != 0:
            print(i + 50)
            buckets[i] -= 1