该小节的知识，重在理解，不需要实现
三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以称为线性排序。
1.桶排序
核心思想：将要排序的数据放入几个有序的桶中，每个桶里的数据单独排序，桶内排序完以后，再把每个桶里的数据依次取出，组成的序列就是有序的。
image.png
时间复杂度分析：
如果要排序的数据有 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)。
桶排序的限制：
- 数据要比较容易的划分为m个桶，并且桶与桶之间要有天然的大小顺序。这样，每个桶内的数据排完后，不需要再排序；
- 数据在各个桶中的分布是比较均匀的，否则集中在某一个桶中，就退化为O(nlogn)
使用场景--外部排序
有10GB的数据要排序，目前内存只有几百M。
- 遍历文件，分析数据的大小，假设数据储存的金额在1到1w元。把数据放在100个桶中(100个小文件)，每个文件的大小约100MB。
- 将数据按照大小依次写到划分的桶(小文件)中，如果某个文件的大小依然超过内存，那么继续划分桶的粒度。
- 依次读取每个小文件到内存中进行排序；
- 依次读取拍好序的文件写到一个新的大文件里面，里面的数据就都是排好序的。
2.基数排序（Radix sort）
场景1：假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？
image.png
- 先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。
- 其中每一位的排序可以借助桶排序，这样总体的时间复杂度在O(n)
场景2：有时候要排序的数据并不都是等长的，比如我们排序牛津字典中的 20 万个英文单词，最短的只有 1 个字母，最长的我特意去查了下，有 45 个字母，中文翻译是尘肺病。对于这种不等长的数据，基数排序还适用吗？
实际上，我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据ASCII 值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。
3.场景拓展
假设我们现在需要对 D，a，F，B，c，A，z 这个字符串进行排序，要求将其中所有小写字母都排在大写字母的前面，但小写字母内部和大写字母内部不要求有序。比如经过排序之后为 a，c，z，D，F，B，A，这个如何来实现呢？如果字符串中存储的不仅有大小写字母，还有数字。要将小写字母的放到前面，大写字母放在最后，数字放在中间，不用排序算法，又该怎么解决呢？
方案一：使用桶排序，小写字母桶/大写字母桶
方案二：使用两个指针，一个指针用来遍历所有的字母，一个指针用来表示大小写字母的分界线
方案三：用两个指针a、b：a指针从头开始往后遍历，遇到大写字母就停下，b从后往前遍历，遇到小写字母就停下，交换a、b指针对应的元素；重复如上过程，直到a、b指针相交。
网友评论