第十三节-线性排序

这节课主要讲了三种线性排序方式：桶排序、计数排序、基数排序。这三种排序都是最好情况下时间复杂度 O(n) 的算法，都对待排数据有特别的要求。

桶排序

桶排序，顾名思义，会用到“桶”。核心思想是将要排序的数据分到几个有序的桶里，再对每个桶里的数据进行单独排序。最后再把每个桶里的数据按顺序连接起来，组成的序列就是有序的了。

对数据的要求：待排数据要能很容易划分成 n 个桶，桶之间有天然的大小顺序。并且数组在各个桶之间的分布是比较均匀的。
时间空间复杂度：假设 n 个数据均匀地分布到 m 个桶内，每个桶就有 k = n/m 个元素。对桶内每个数据使用快排，总时间复杂度 O(m * k * logk) = O(n * log(n/m))。当 m 接近 n 时，时间复杂度为 O(n)。当数据分布很不均匀时，时间复杂度会退化到 O(nlogn)。
应用场景：可以用于外部排序。

比如用几百 M 内存排序 10GB 的订单数据（假设金额都是正整数）。

我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 到 1000 元之间的订单，第二桶存储金额在 1001 元到 2000 元之间的订单，以此类推。每一个桶对应一个文件，并且按照金额大小顺序命名（00，01，02…99）。

在理想情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小打到排序的订单数据了。

不过，订单金额很可能是分布极不均匀的，若是集中在某个区间，比如 1 到 1000 元中间比较多，那我们还可以对这个区间再进行具体的划分，比如 1 到 100 是一个区间，101 到 200 是第二个区间，以此类推。如果划分之后，某个区间的订单仍然太多，那还可以继续划分，直到所有文件都可以读入内存为止。

计数排序

计数排序应该是桶排序的一种比较特殊的情况。这种情况要求待排序的数据集中在一个不大的范围内，比如最大值是 K ，我们就可以把数据分成 K 个桶，每个桶里的数据都是相同的，省掉了桶内排序的时间。若有负数，还需要设置偏移量。

对数据的要求：数据集中在一个较小的范围内。
时间空间复杂度：时间复杂度是 O(n)。只有只有三趟遍历，第一趟计数，第二趟映射到辅助数组，第三趟拷贝回原数组。空间复杂度是 O(n)，虽然省掉了桶内排序的时间，但是空间没有减少。
应用场景：比如对高考考生成绩排序，只有几百种情况，直接开几百个桶就可以了。

基数排序

是一种多关键字排序方法。从关键字的后部往前进行多轮 O(n) 的稳定性排序排序。

对数据的要求：待排数据的键值部分可以分成几个部分。
时间空间复杂度：总时间复杂度是键值部分个数 m 的 O(n) 倍，由于键值部分个数一般是一个很小的常量，所以，总时间仍是 O(n)。空间复杂度是 O(n)。
应用场景：对手机号进行排序。键值部分个数是 11 个，总共进行 11 趟。其他情况若是关键字部分长度不一，可以采用填充法。

课后思考

根据年龄给 100 万用户排序

使用桶排序，开 120 个桶，看情况要不要进行外部排序。

对包含大写字母、小写字母、数字的一个字符串按照小写字母在前，大写字母在最后，数字在中间，不用排序算法进行排列。

这是一个荷兰国旗问题。

使用三个指针，pre, current, last 分别指向小写字母部分的结尾，数字部分的开头，大写字母部分的开头，采用交换元素的方法，遍历一遍待排字符串即可。时间复杂度 O(n)，空间复杂度 O(1)。