排序-线性排序,如何做到百万级数据秒级排序，时间复杂度O(n)？

2019 年 10 月 29 日
筆記

我们经常接触的冒泡排序，快速排序，归并排序等，这些排序时间复杂度大多是n^2或者N(logN),他们都是基于比较的排序(就是排序过程中数据两两做比较)，那你有知道和了解几种线性排序的算法吗？他们的时间复杂度都是O(n),下面的几个问题你会了吗？

问题

1000万订单数据金额如何O(n)复杂度排序？
100万考生成绩如何O(n)复杂度秒级排序？
100个手机号如何从小到达O(n)复杂度排序？

常见的线性排序

桶排序

桶排序，顾名思义就是把要排序的元素放入各个桶中，然后每个桶中的元素再进行排序，这样最后所有桶中的元素按桶的顺序排列，则所有元素有序，我们假设n个元素，m个桶，那么每个桶中放入(n/m=k)个元素,每个桶中元素的排序可以用之前我们分享过的快速排序，则桶排序的时间复杂度是m * k(logk),我们把k用n/m进行等价替换，所以时间复杂度就编程了 n* log(n/m)，当m非常接近n时，那么桶排序的时间复杂度就是O(n)了。

1000万订单数据金额排序答疑：我们来看上面1000万订单数据金额排序的问题，假设我们只有10M内存，我们首先遍历一遍文件，得出金额的最大值，假设最大值50000，也就是说1000万订单数据金额最小值是0，最大值是50000，那么我们对0到50000的金额大小划分1000个桶，把0到50的金额第一个桶，50到100的金额放入第二个桶，以此类推，然后对每个桶的数据进行排序，之后写入磁盘文件，命名为bucket050.txt，以此类推，直到所有桶的数据都排序完毕,排序过程中，当某一个桶的数据过大，10M内存放不下时，可以用同样的思想进行拆分为多个桶，用下面的图描述一个这个过程。

桶排序的示例代码:

计数排序

计数排序跟上面的桶排序非常的类似，我们提到上面每个桶放入的元素是(k=n/m)，假设这个k=1，那么相当于每个桶的元素就只有一个，试想一下，我们是不是只要遍历原始数据，就相当于排序完成。

分析下100万考生成绩O(n)复杂度秒级排序

100万考生，看着数据量很大，但我们透过现像看本质，这些数据的最大值是多少呢?750，是的，高考成绩最大值750，最小值0，也就是说我我们只需要751个桶，我们声明一个长度为751的数组，代表751个桶，数组的下标就是考生的成绩，然后我们100万数据遍历，数组的值是这个成绩出现的次数，当100万数据遍历完成后，我们遍历我们创建的这个桶，根据数组中的值确定打印数组下标的次数，结果就是这100考生成绩的排序。我们看代码实现。

我们看下边的图，就能理解上面代码的逻辑了

那么为什么要叫做计数排序呢？如果我想知道上图中result结果中值为2元素的下标在什么位置？该怎么获取呢？你有好的想法吗

首先我们对上图中的bucket的数组顺序求和，得到如下

我们从后往前依次遍历数组param中的元素，当遍历到1时，我我们从求和后的bucket数组中获取下标为1的元素2，也就说到现在为止，包含自己在内的小于等于1的元素只有2个，也就是说1是数组result中的第二个元素，这时小于等于1的元素就只剩1个了，当我们遍历完数组param，得到的结果就是排列有序的了。