数据结构与算法之美-排序(三) 数据结构与算法之美-排序(三

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

前面学的排序都是基于比较的排序算法，桶排序、计数排序、基数排序不是基于比较的排序算法，不涉及元素之间的比较操作，所以时间复杂度是线性的，称为线性排序。

1. 桶排序 1.1 核心思想 【数据结构与算法之美-排序(三)】将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

文章图片
image.png 1.2 时间复杂度分析待排序的数据有 n 个，均匀的分到 m 个桶内，每个桶里有k = n/m个元素。桶内部使用快排，时间复杂度为O(k * logK)。m 个桶排序的时间复杂度就是O(m * k *logk)，因为k=n/m，所以整个桶排序的时间复杂度为 O(n*log(n/m))，当桶的个数 m 接近数据个数 n 时，log(n/m)就是一个非常小的常量，桶排序的时间复杂度就接近 O(n)了。
1.3 适用场景

排序的数据需要很容易能划分成 m 个桶
桶之间有着天然的大小顺序，这样桶内的数据排完序之后，桶和桶之间不需要再次排序
数据在各个桶之间分布比较均匀
适合用在外部排序（数据存储在外部磁盘，数据量比较大，内存优先，无法将数据全部加载到内存）中

1.4 举例有 10GB 的订单数据，希望按订单金额进行排序，但是内存有限，只有几百 MB，无法一次性将 10GB 的数据加载到内存，可以借助桶排序的处理思想去解决这个问题。
方案：

先扫描一遍文件，看订单金额所处的数据范围；
将订单根据金额划分到不同的桶里，比如上面扫描之后订单金额为 1元到 10 万元不等，可以将所有订单根据金额划分到 100 个桶里，每个桶存储的最大最小金额差为 1000，每一个桶对应一个文件，并且按照金额范围大小顺序编号命名；
将每个桶（文件）依次加载到内存，使用快排排序；
按照文件编号，从小到大依次取出每个小文件中的订单数据，并将其写入到一个总文件。

上面的解决方案是针对于订单按照金额 1 元到 10 万元之间是均匀分布的，如果不满足这个条件呢？比如有可能某个金额区间的数据特别多，还是没有办法一次读取到内存。

针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在 1 元到 1000 元之间的比较多，我们就将这个区间继续划分为 10 个小区间，1 元到 100 元，101 元到 200 元，201 元到 300 元....901 元到 1000 元。如果这次划分之后有的区间还是太多，那么就继续划分，直到所有的文件都能读入内存为止。
2. 计数排序 2.1 核心思想计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值为 k，就可以把数据划分成 k 个桶，每个桶内的数据值都是相同的，省掉了桶内排序的时间。
2.2 举例高考有50 万考生，如何通过成绩快速排序得出名次？
满分为 900 分，最小为 0 分，数据范围很小，可以划分为 901 个桶，对应分数从 0 到 900 分，根据考生成绩，将 50 万考生划分到这 901 个桶里，桶内的数据都是分数相同的考生，所以桶内就不需要排序了。只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序，只涉及到遍历操作，所以时间复杂度为 O(n)。

计数排序的算法思想就是这么简单，跟桶排序类似，只是桶的大小粒度不同。为什么称为"计数"排序呢？“计数”的含义怎么体现？

假设只有 8 个考生，分数在 0 - 5分之间，成绩存储在一个数组 A[8]中，2 5 3 0 2 3 0 3。
我们创建一个 C[6] 表示桶，数组下标对应分数，每个下标对应的是考生的个数，只需要遍历一遍考生分数，就可以得到 C[6]的值：

文章图片
image.png 从图中可以看出，分数为 3分的考生有 3 个，小于 3 分的考生有 4 个，所以，成绩为 3 分的考生在排序之后的有序数组 R[8] 中，会保存在下标 4 5 6 的位置：

文章图片
image.png 那如何快速计算出每个分数的考生在有序数组中对应的存储位置呢？
就是对 C[6]数组顺序求和，C[6]存储的数据就变成了下面这个样子，C[k]里存储小于等于分数 K 的考生个数：

文章图片
image.png 我们从后到前(保证计数排序的稳定性)依次扫描数组 A[8]，当扫描到 3 时，可以从数组 C 中取出下标为 3 的值 7，也就是说，包括自己在内，分数小于等于 3 的考生有 7 个，也就是说 3 是数组 R 中的第 7 个元素（也就是数组 R 中下标为 6 的位置）。当 3 放入到数组 R 中后，小于等于 3 的元素只剩下 6 个了，所以相应的 C[3]要减 1，变成6。
以此类推，当扫描到第 2 个分数为 3 的考生的时候，就把它放入数组 R 中的第 6 个元素的位置（下标为 5 的位置）。当扫描完整个数组 A 后，数组 R 内的数据就是按照分数从小到大有序排列的了。
image.png 实现代码如下：

// 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。 public void countingSort(int[] a, int n) { if (n <= 1) return; // 查找数组中数据的范围 int max = a[0]; for (int i = 1; i < n; ++i) { if (max < a[i]) { max = a[I]; } }int[] c = new int[max + 1]; // 申请一个计数数组c，下标大小[0,max] for (int i = 0; i <= max; ++i) { c[i] = 0; }// 计算每个元素的个数，放入c中 for (int i = 0; i < n; ++i) { c[a[i]]++; }// 依次累加 for (int i = 1; i <= max; ++i) { c[i] = c[i-1] + c[I]; }// 临时数组r，存储排序之后的结果 int[] r = new int[n]; // 计算排序的关键步骤，有点难理解 for (int i = n - 1; i >= 0; --i) { int index = c[a[i]]-1; r[index] = a[I]; c[a[i]]--; }// 将结果拷贝给a数组 for (int i = 0; i < n; ++i) { a[i] = r[I]; } }

2.3 适用场景

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适用了
计数排序只能给非负整数排序，如果要排序的数据为其他类型，则需要转化为非负整数

3. 基数排序 3.1 举例

假设有 10 万个手机号码，要进行排序，有什么比较快速的排序方法？

手机号 11 位，范围太大，上面讲的两种排序算法，都不适用，可以考虑基数排序。
上面的问题有这样的规律：假设要比较两个手机号码 a b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面几位就不用看了。
借助稳定排序算法，可以先按照最后一位来排序手机号码，然后再按照倒数第二位重新排序，以此类推，经过 11 次排序之后，手机号码就都有序了。
以字符串排序为例，基数排序的过程分解图：

文章图片
image.png

这里按照每位来排序的排序算法必须是稳定的，因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的顺序，之前低位排序就没有意义了。

根据每一位来排序，这一步可以使用上面提到的桶排序或者计数排序，它们的时间复杂度可以做到 O(n)，如果要排序的数据有 K 位，那么就需要 K 次桶排序或者计数排序，总的时间复杂度为 O(k*n)，当 k 不大的时候，基数排序的时间复杂度就近似于 O(n)。
有时候要排序的数据并不都是等长的，可以将所有数据补齐到相同的长度，位数不够的用 0 来凑。
3.2 适用场景

对排序数据要求较高，可以分割出独立的“位”来比较；
且“位”之间有递进关系；
每一位的数据范围不能太大，要可以用线性排序算法来排序。

4. 总结桶排序、计数排序、基数排序对于排序数据有很高的要求，应用不是很广泛，但是满足这个条件之后，时间复杂度可以达到 O(n)。
桶排序和计数排序思想相同，将数据划分为不同的桶来实现。
基数排序要求数据可以划分为高低位，位之间有递进关系，且每一位的数据范围不能太大，因为基数排序算法需要借助桶排序或者计数排序来完成每一个位的排序工作。