常用排序算法总结(2)非比较排序算法:计数排序,基数排序,桶排序


来自:SteveWang

上一篇总结了常用的比较排序算法,主要有冒泡排序选择排序插入排序归并排序堆排序快速排序等。

这篇文章中我们来探讨一下常用的非比较排序算法:计数排序基数排序桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。

这里我们用到的唯一数据结构就是数组,当然我们也可以利用链表来实现下述算法。

计数排序(Counting Sort)

计数排序用到一个额外的计数数组C,根据数组C来将原数组A中的元素排到正确的位置。

通俗地理解,例如有10个年龄不同的人,假如统计出有8个人的年龄不比小明大(即小于等于小明的年龄,这里也包括了小明),那么小明的年龄就排在第8位,通过这种思想可以确定每个人的位置,也就排好了序。当然,年龄一样时需要特殊处理(保证稳定性):通过反向填充目标数组,填充完毕后将对应的数字统计递减,可以确保计数排序的稳定性。

计数排序的步骤如下:

  1. 统计数组A中每个值A[i]出现的次数,存入C[A[i]]

  2. 从前向后,使数组C中的每个值等于其与前一项相加,这样数组C[A[i]]就变成了代表数组A中小于等于A[i]的元素个数

  3. 反向填充目标数组B:将数组元素A[i]放在数组B的第C[A[i]]个位置(下标为C[A[i]] – 1),每放一个元素就将C[A[i]]递减

计数排序的实现代码如下:

下图给出了对{ 4, 1, 3, 4, 3 }进行计数排序的简单演示过程


计数排序的时间复杂度和空间复杂度与数组A的数据范围(A中元素的最大值与最小值的差加上1)有关,因此对于数据范围很大的数组,计数排序需要大量时间和内存。

例如:对0到99之间的数字进行排序,计数排序是最好的算法,然而计数排序并不适合按字母顺序排序人名,将计数排序用在基数排序算法中,能够更有效的排序数据范围很大的数组。

基数排序(Radix Sort)

基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机上的贡献。它是这样实现的:将所有待比较正整数统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始进行基数为10的计数排序,一直到最高位计数排序完后,数列就变成一个有序序列(利用了计数排序的稳定性)。

基数排序的实现代码如下:

下图给出了对{ 329, 457, 657, 839, 436, 720, 355 }进行基数排序的简单演示过程


基数排序的时间复杂度是O(n * dn),其中n是待排序元素个数,dn是数字位数。这个时间复杂度不一定优于O(n log n),dn的大小取决于数字位的选择(比如比特位数),和待排序数据所属数据类型的全集的大小;dn决定了进行多少轮处理,而n是每轮处理的操作数目。

如果考虑和比较排序进行对照,基数排序的形式复杂度虽然不一定更小,但由于不进行比较,因此其基本操作的代价较小,而且如果适当的选择基数,dn一般不大于log n,所以基数排序一般要快过基于比较的排序,比如快速排序。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序并不是只能用于整数排序。

桶排序(Bucket Sort)

桶排序也叫箱排序。工作的原理是将数组元素映射到有限数量个桶里,利用计数排序可以定位桶的边界,每个桶再各自进行桶内排序(使用其它排序算法或以递归方式继续使用桶排序)。

桶排序的实现代码如下:

下图给出了对{ 29, 25, 3, 49, 9, 37, 21, 43 }进行桶排序的简单演示过程


桶排序不是比较排序,不受到O(nlogn)下限的影响,它是鸽巢排序的一种归纳结果,当所要排序的数组值分散均匀的时候,桶排序拥有线性的时间复杂度。

推荐↓↓↓
算法与数据结构
上一篇:常用排序算法总结(1)冒泡、选择、插入、希尔排序、归并排序、堆排序、快排 下一篇:推荐一本设计模式方面的图书——《大话设计模式》