1 线性排序 1.1 桶排序
《算法导论3rd-p112》
将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
1.1.1 桶排序的使用前提
首先，要排序的数据需要很容易就能划分成 m 个桶(如何合理选择桶的数量？)，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。
1.1.2 桶排序的适用场景
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？如何借助桶排序的处理思想来解决这个问题？
我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02...99）。
理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。
不过，订单按照金额在 1 元到 10 万元之间并不一定是均匀分布的 ，所以 10GB 订单数据是无法均匀地被划分到 100 个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢？针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在 1 元到 1000 元之间的比较多，我们就将这个区间继续划分为 10 个小区间，1 元到 100 元，101 元到 200 元，201 元到 300 元....901 元到 1000 元。如果划分之后，101 元到 200 元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。
1.1.3 如何计算桶排序中桶的数量？
已知 vector nums，如何计算桶的数量//方法一int n = nums.size();int minVal = *min_element(nums.begin(), nums.end());int maxVal = *max_element(nums.begin(), nums.end());//将最大值与最小值之差按照数据个数进行均分，这里的d就相当于单个桶的容量，也就是桶的大小//求出的d用来求解桶的索引int d = max(1, (maxVal - minVal) / (n - 1));//桶的大小int bucketSize = (maxVal - minVal) / d + 1;//计算桶的索引int idx = (nums[i] - minVal) / d;//方法二int n = nums.size();int minVal = *min_element(nums.begin(), nums.end());int maxVal = *max_element(nums.begin(), nums.end());//桶的大小int bucketSize = (maxVal - minVal) / n + 1;
1.2 计数排序
《算法导论3rd-p108》
计数排序是特殊的桶排序，待排序的数据的取值范围都在[0,k]范围内，此时可把数据放入k+1个桶中，每个桶中的数据都是相同的，省掉了桶内排序。
计数排序需要额外的空间来保存计数数据(下面代码中的counter)，故计数排序不是原地排序；计数排序是稳定的排序，代码中有体现。
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
//out中是已经排序好的数据//k表示nums中的数据的取值范围为[0, k],使用k+1个桶，每个桶内的数据都相同，省掉了桶内的排序void countingSort(vector& nums, vector& out, int k){vector counter(k+1, 0);//保存数据出现的次数for (auto& i:nums){counter[i]++;}//更新counter[i]，使得其内保存的是值小于等于i的总次数for (int i=1;i<=k;++i){counter[i] += counter[i - 1];}//输出到out，逆序访问nums中的数据，保证稳定性out.resize(nums.size());for (auto it=nums.rbegin(); it != nums.rend(); ++it){//注意索引比次数少一out[counter[*it]-1] = *it;counter[*it]--;}}
1.3 基数排序
《算法导论3rd-p110》
基数排序是基于计数排序的来实现的，所以基数排序也不是原地排序；由于计数排序是稳定的，所以基数排序也是稳定的。
1.3.1 基数排序思路分析
这里有一个新的排序问题。假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？
如果使用快排，时间复杂度可以做到 O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序能派上用场吗？手机号码有 11 位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法呢？
现在就来介绍一种新的排序算法，基数排序。刚刚这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。借助稳定排序算法，这里有一个巧妙的实现思路。先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。一个简单的例子见下图：
1.3.2 基数排序适用范围
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
2 题目 2.1 最大间距
164、最大间距
2.1.1 基数排序进行求解
class Solution {public: int maximumGap(vector& nums) { //方法一：基数排序，https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode-solution/ int n = nums.size(); if (n < 2) { return 0; } int exp = 1; vector buf(n); int maxVal = *max_element(nums.begin(), nums.end()); while (maxVal >= exp) { //基数排序是基于计数排序的，会用到额外的空间来保存计数数据 //由于十进制数每位的取值范围为[0,9]，对应于计数排序中的k=9，所以这里的cnt需要预留10个元素的存储空间 vector cnt(10, 0); for (int i = 0; i < n; ++i) { int digit = (nums[i] / exp) % 10; cnt[digit]++; } //更新cnt[i]，使得其内保存的是值小于等于i的总次数 for (int i = 1; i < 10; i++) { cnt[i] += cnt[i - 1]; } //将排序后的数据保存到buf，逆序访问nums中的数据，保证稳定性 for (int i = n - 1; i >= 0; i--) { int digit = (nums[i] / exp) % 10; //索引比次数少一 buf[cnt[digit] - 1] = nums[i]; cnt[digit]--; } //此时buf保存的是按位进行过一轮排序后的数据，需要对其进行下一轮的排序 nums.swap(buf); exp *= 10; } int ret = 0; for (int i = 1; i < n; i++) { ret = max(ret, nums[i] - nums[i - 1]); } return ret; }};
2.1.2 桶排序进行求解
//桶排序，https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode-solution/class Solution {public: int maximumGap(vector& nums) { int n = nums.size(); if (n < 2) { return 0; } int minVal = *min_element(nums.begin(), nums.end()); int maxVal = *max_element(nums.begin(), nums.end()); int d = max(1, (maxVal - minVal) / (n - 1)); int bucketSize = (maxVal - minVal) / d + 1; vector> bucket(bucketSize, {-1, -1}); // 存储 (桶内最小值，桶内最大值) 对，(-1, -1) 表示该桶是空的 for (int i = 0; i < n; i++) { int idx = (nums[i] - minVal) / d; if (bucket[idx].first == -1) { bucket[idx].first = bucket[idx].second = nums[i]; } else { bucket[idx].first = min(bucket[idx].first, nums[i]); bucket[idx].second = max(bucket[idx].second, nums[i]); } } int ret = 0; int prev = -1; for (int i = 0; i < bucketSize; i++) { if (bucket[i].first == -1) continue; if (prev != -1) { //相邻元素之间最大的差值 ret = max(ret, bucket[i].first - bucket[prev].second); } prev = i; } return ret; }};
2.2
2.3