线性时间排序总结

向右看齐 2022-01-13 12:15 188阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

## **计数排序** ##

计数排序（counting sort）的思路很简单，就是确定比x小的数有多少个。加入有10个，那么x就排在第11位。

严谨来讲，在计算机科学中，计数排序是一个根据比较键值大小的排序算法，它也是一个整数排序算法。它通过比较对象的数值来操作，并通过这些计数来确定它们在即将输出的序列中的位置。它的运行时间是线性的且取决于最大值和最小值之间的差异，当值的变化明显大于数目时就不太适用了。而它也可以作为基排序的子程序。

![170245\_Vcia\_3702502.png][170245_Vcia_3702502.png]

第2-3步，C数组的元素被全部初始化为0，此时耗费Θ(k)时间。

第4-5步，也许不太好想象，其实就是在C数组中来计数A数组中的数。比如说，A数组中元素”3”有4个，那么C\[3\]=4。此时耗费Θ(n)时间。

第7-8步，也是不太好想象的计算，也就是说如果C\[0\]=1、C\[1\]=4，那么计算后的C\[0\]不变，C\[1\]=5。此时耗费Θ(k)时间。

第10-12步，把每个元素A\[j\]放到它在输出数组B中的合适位置。比如此时的第一次循环，先找到A\[8\]，然后找到C\[A\[8\]\]的值，此时C\[A\[8\]\]的意义就在于A\[8\]应在B数组中的位置。完成这一步后将C\[A\[8\]\]的值减一，因为它只是一个计数器。这里耗费的时间为Θ(n)。

当k=O(n)时，计数排序的运行时间为Θ(n)。

## **基数排序** ##

基数排序（radix sort）是一个古老的算法，它用于卡片排序机上。说来也巧，写这篇博客的前一天晚上还在书上看到这种机器，它有80列，每一列都有12个孔可以打。

它可以使用前面介绍的计数排序作为子程序，然而它并不是原址排序；相比之下，很多运行时间为Θ(nlgn)的比较排序却是原址排序。因此当数据过大而内存不太够时，使用它并不是一个明智的选择。

![这里写图片描述][20150611111819004]

关键在于依次对从右往左每一列数进行排序，其他的列也相应移动。

## **桶排序** ##

这倒是一个有趣的算法了，它充分利用了链表的思想。

桶排序（bucket sort）在平均情况下的运行时间为O(n)。

计数排序假设n个输入元素中的每一个都在0和k之间，桶排序假设输入数据是均匀分布的，所以他们的速度都非常快。但并不能因为这些是假设就说它们不实用不准确，真正的意义在于你可以根据情况选择合适的算法。比如说，输入的n个元素并不是均匀分布的，但它们都在0到k之间，那么就可以用计数排序。

说到桶，我想到的是装满葡萄酒的酒桶以及装满火药的火药桶。这里是桶是指的算法将\[0,1)区域划分为了n个相同大小的空间，它们被称为桶。

既然有了这个划分，那么就要用到它们。假设输入的是n个元素的数组A，且对于所有的i都有0≤A\[i\]<1。你也许会觉得怎么可能输入的数组元素都凑巧满足呢，当然不会这么凑巧，但是你可以人为地改造它们呀。比如<10,37,31,87>，你可以将它们都除以100，得到<0.10,0.37,0.31,0.87>。

还需要一个临时的数组B\[0…n-1\]来保存这些桶（也就是链表），而链表支持搜索，删除和插入。关于链表的部分后面的博客中会有详细介绍。

![170351\_msUj\_3702502.png][170351_msUj_3702502.png]

![这里写图片描述][20150611123650732]

总结自：http://blog.csdn.net/nomasp/article/details/50359787

转载于:https://my.oschina.net/u/3702502/blog/1601274

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220113/009a4e62fcf9409b804d9ed8d39e4b09.png
[170245_Vcia_3702502.png]: https://static.oschina.net/uploads/space/2018/0103/170245_Vcia_3702502.png
[20150611111819004]: /images/20220113/3899f43f9bb2495a81f3dce8c1cf9c12.png
[170351_msUj_3702502.png]: https://static.oschina.net/uploads/space/2018/0103/170351_msUj_3702502.png
[20150611123650732]: /images/20220113/6948a92cbefe40ccaad528e4e8b00ce1.png