13 | 线性排序：

桶排序（Bucket sort）

比较适合用在外部排序中

计数排序（Counting sort）

可以理解为是桶排序的特殊情况。

当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

每一分都是一个桶

从后到前扫描数组。计数排序是一个稳定排序算法。这也就是为啥从后开始遍历的原因。因为这样使得原数组里在后的元素，在排序后的数组也放在后边。

A中的元素的值对应C的下标，（代码中也是把A数组里面的元素作为C的下标），找C中的那个元素，清楚A中这个元素的顺序

知道顺序后就可以填入R数组中

当 3 放入到数组 R 中后，小于等于 3 的元素就只剩下了 6 个了，所以相应的 C[3]要减 1，变成 6。

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

基数排序（Radix sort）

例子：手机号大小的排序，优先保证前几位够大，后几位就不用考虑了，但排序是是从后位开始排序

高位排序时是稳定排序，这样能保证相同高位的低位是按照次序排的

手机号或者单词长度不同时在后面补零即可，因为ascii码最小。

课后思考

我们今天讲的都是针对特殊数据的排序算法。实际上，还有很多看似是排序但又不需要使用排序算法就能处理的排序问题。假设我们现在需要对 D，a，F，B，c，A，z 这个字符串进行排序，要求将其中所有小写字母都排在大写字母的前面，但小写字母内部和大写字母内部不要求有序。比如经过排序之后为 a，c，z，D，F，B，A，这个如何来实现呢？如果字符串中存储的不仅有大小写字母，还有数字。要将小写字母的放到前面，大写字母放在最后，数字放在中间，不用排序算法，又该怎么解决呢？

用两个指针a、b：a指针从头开始往后遍历，遇到大写字母就停下，b从后往前遍历，遇到小写字母就停下，交换a、b指针对应的元素；重复如上过程，直到a、b指针相交。
对于小写字母放前面，数字放中间，大写字母放后面，可以先将数据分为小写字母和非小写字母两大类，进行如上交换后再在非小写字母区间内分为数字和大写字母做同样处理

版权声明：笔记部分摘抄自极客时间中的课程及评论区