线性排序

线索：

1. 说说桶排序的思想、桶排序的适用场景；

2. 说说计数排序的思想、计数排序的算法的巧妙实现、计数排序的适用场景；

3. 说说基数排序的思想、基数排序的适用场景。

桶排序 BucketSort

1. 桶排序。

桶排序的思想是，将待排序序列划分到几个有序的桶中，然后分别对每个桶的数据单独排序。最后按照桶的顺序依次将桶里的元素取出，最后组成的序列就是有序的了。

桶排序是线性排序，时间复杂度是 O(N)

我们将 n 个数据划分到 k 个桶中，然后对每个桶单独进行快排。可以得到：O(k * n/k * log(n/k) )=O(n * log(n/k) )，当桶的数量 k 接近数据个数 n 时，log(n/k) 就是一个非常小的常量，此时桶排序的时间复杂度接近 O(N)

2. 桶排序的适用场景。

①待排序序列能轻易的划分出 n 个桶，并且桶与桶之间天然有大小顺序；

②数据比较均匀地分布在各个桶中；极端情况下都分布在一个桶中，退化成 O(NlogN)

③桶排序适用于外部排序。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

3. 假设我们有 10GB 的订单数据，我们希望按照订单金额大小排序。而这 10G 的数据无法一次性加载进内存，此时我们可以借助桶排序。

首先，扫描一遍文件，得到订单金额所处的范围，假设最小值为 1，最大值是 10 万。

接着，我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元的订单，以此类推。

理想的情况下，订单金额均匀分布，订单会被均匀地划分到 100 个文件中，每个小文件大约 100MB，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。

最后依次取出桶里边的每个元素输出到一个文件夹中。当然，订单金额不均匀，可能出现单个桶太大无法加载至内存中，我们可以按照同样的思路，对这个桶继续划分，比如是[1,1000]的桶太大，那么我们可以将[1,1000]的桶划分成 10 个区间。[1,100]、[101,200]……直至所有桶都能读进内存为止。

基数排序 RadixSort

1. 基数排序。

假设我们要对 10 万个手机号码进行排序，手机号码有 11 位，范围太大（ ），显然桶排序和计数排序是不适合用。

类似手机号码的排序，是有规律的，比如 a 前几位比 b 大，那么后面几位就可以不用看了。

借助稳定排序算法，我们可以先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。// 基数排序的实现思路。

注意，这里要使用稳定的排序算法，因为到排序第一位时，如果是不稳定的排序算法，那么我们之前所排序的低位就没有了意义。

// 基数排序的时间复杂度。

根据每一位来排序，我们可以用桶排序或计数排序，它们的时间复杂度可以做到 O(N)。如果要排序的数据有 k 位，那我们就需要 k 次桶排序或计数排序，总的时间复杂度是 O(k*n)。当 k 不大的时，比如手机号码排序的例子，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。

有时候排序的数据并不都是等长的，比如排序牛津词典。这个时候我们可以将所有单词补齐到相同长度。位数不够的在后面补“0”，因为根据 ASCII 值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。

// 注意，字典中的顺序不考虑长度，比如 abf 排在 abbs 前面。

2. 基数排序的适用场景。

①待排序数据可以分割出独立的“位”来比较，且位之间有递进的关系。比如电话号码。

②每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。// 计数排序的要求是范围不能太大

计数排序 CountingSort

1. 计数排序。

计数排序是一种特殊的桶排序，它和桶排序十分类似，只是桶粒度不一样。

计数排序的思想是，如果待排序的 n 个数据的数据范围不大时，比如最大值是 k，然后我们将这 n 个数据划分到 k 个桶中，每个桶的数据值都相同，这样就省去了桶内排序的时间。

比如高考查分系统，能显示我们成绩以及所在省的排名。

假设有 50 万考生，分数在[0,900]，这个数据范围很小，我们可以分成 901 个桶，然后根据考生的成绩，将这 50 万考生划分到这 901 个桶里。

由于桶内元素都相同，因此我们只需依次遍历每个桶，然后将其输出到一个数组中。就实现了 50 万考生的排序。

整个过程只涉及扫描遍历的操作，所以时间复杂度是 O(N)

2. 计数排序的代码实现。

假设有考生 8 名，分数在 0 到 5 分之间。数组 A 存储学生成绩。A[8] = {2，5，3，0，2，3，0，3}// 待排序数组

由于分数在[0,5]，因此我们用 C[6]表示桶。C[i]表示分数为 i 考生的个数。扫一遍数组 A 我们就能得到 C[6] = {2,0,2,3,0,1}

接着对 C[6]进行顺序求和，C[6] = {2,2,4,7,7,8}，此时 C[i]表示分数小于等于 i 的人数。

接着从后向前遍历数组 A，比如第一个是 3，然后回到数组 C 中，C[3]=7，对应的是包括自己分数小于等于 3 的有 7 人，因此存储到数组 R[6]（第 7 位），然后--C[3]。// 即存储到 R[--C[3]]

最后将数组 R 拷贝回数组 A。

3. 计数排序的适用场景。

①数据范围不大。如果数据范围 k 比待排序数据数量 n 大很多，则不适合用计数排序。

②数据为非负的整数。这是由计数排序的代码实现决定的。

因此，如果待排序数据不是非负整数，我们需要将其在不改变相对大小的情况下，转化为非负整数。

比如，如果考生成绩精确到小数后一位，我们就需要将所有的分数都先乘以 10，转化成整数，然后再放到 9010 个桶内。再比如，如果要排序的数据的范围是[-1000, 1000]，那我们就需要先对每个数据都加 1000，转化成非负整数。