排序算法下——桶排序、计数排序和基数排序
桶排序、计数排序和基数排序这三种算法的时间复杂度都为
，因此，它们也被叫作线性排序（Linear Sort）。之所以能做到线性，是因为这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。
1. 桶排序（Bucket Sort）？
1.1. 桶排序原理
- 桶排序，顾名思义，要用到“桶”。核心思想是将要排序的数据分到几个有序的桶里，每个桶的数据再单独进行排序。桶内排完序后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
桶排序
1.2. 桶排序的时间复杂度分析
- 如果要排序的数据有
个，我们把它们均匀地划分到
个桶内，每个桶内就有
个元素。对每个桶内的数据进行快速排序，时间复杂度为
。
。当桶的个数接近数据个数时，
就是一个非常小的数，这个时候通排序的时间复杂度接近于
1.3. 桶排序的适用条件
桶排序看起来很优秀，但事实上，桶排序对排序数据的要求是非常苛刻的。
- 首先，要排序的数据需要很容易就能划分为
- 其次，数据在各个桶之间的分布是比较均匀的。
- 桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据比较大而内存有限，无法将数据全部加载到内存中去。
1.4. 一个桶排序的实例
假如我们有 10 GB 的订单数据需要按照金额进行排序，但内存只有几百 MB ，这时候该怎么办呢？
-
我们先扫描一遍文件，确定订单金额的数据范围。
-
如果扫描后发现订单金额处于 1 万元到 10 万元之间，我们将所有订单按照金额划分到 100 个桶内，第一个桶数据范围为[1, 1000]，第二个桶数据范围为[1001, 2000]......，每个桶对应一个文件，同时将文件按照金额范围的大小顺序编号命名（如00、01、02...99）。
-
如果订单金额分布均匀，则每个文件包含大约 100 MB 的数据，我们可以将每个小文件读入到内存中，进行快速排序。然后，再按顺序从各个小文件读取数据，写入到另外一个文件，即是排序好的数据了。
-
如果订单分布不均，某一范围内数据特别多无法一次读入内存，则可以继续对此区间再进行划分，直到所有的文件都可以读入内存为止。
2. 计数排序（Counting Sort）？
2.1. 计数排序算法实现
-
计数排序可以看作是桶排序的一种特殊情况。当要排序的数据所处的范围并不大时，比如最大值为
，这时候，我们可以把数据分为
-
假设高考分数的范围为 [0, 750]，我们可以将考生的分数划分到 751 个桶内，然后再依次从桶内取出数据，就可以实现对考生成绩的排序了。因为只涉及到扫描遍历操作，因此时间复杂度为
但这个排序算法为什么叫计数排序呢，这是由计数排序算法的实现方法来决定的，我们来看一个简单的例子。
-
假设有 8 个考生，他们的分数范围为 [0, 5]。这 8 个考生的成绩我们放在一个数组中，A[8] = {2, 5, 3, 0, 2, 3, 0, 3}。
-
我们用大小为 6 的数组代表 6 个桶来统计考生的成绩分布情况，其中下标表示考生的分数，数组内的值表示这个分数的考生个数。我们遍历一遍数组后，就可以得到 C[6] = {2, 0, 2, 3, 0, 1,}，得 0 分的共有 2 人，得 3 分的共有 3 人。
-
如下所示，成绩为 3 的考生共有 3 个，小于 3 分的考生共有 4 个，所以在排好序的数据 R[8] 中，3 的位置应该为 4，5 和 6 。
R[8]
- 而我们怎么得到这个位置呢？只需要对 C[6] 数组按顺序累计求和即可，这时候，C[6] 数组中的每个值就都表示小于等于它的值的个数了。
C[6]
-
接下来，我们从后到前依次扫描数组 A[8]。当扫描到 3 时，我们取出 C[3] 的值 7，说明小于等于 3 的个数为 7 个，那么 3 就应该放在数组 R[8] 的第 7 个位置，也就是下标为 6 的地方。当我们再次遇到 3 的时候，这时候小于等于 3 的元素个数就少了一个，也就是我们要把 C[3] 相应地减去 1 。
-
之所以要从后到前依次扫描数组，是因为这样之前相同的元素就仍然会保持相同的顺序，可以保证排序算法的稳定性。
-
当我们扫描完整个数组 A[8] 时，数组 R[8] 中的数据也就从小到大排好序了，其详细过程可参考下图。
计数排序
- 代码实现
// 假设数组中存储的都是非负整数
void Counting_Sort(int data[], int n)
{
if (n <= 1)
{
return;
}
// 寻找数组的最大值
int max = data[0];
for (int i = 1; i < n; i++)
{
if (data[i] > max)
{
max = data[i];
}
}
// 定义一个计数数组, 统计每个元素的个数
int c[max+1] = {0};
for (int i = 0; i < n; i++)
{
c[data[i]]++;
}
// 对计数数组累计求和
for (int i = 1; i <= max; i++)
{
c[i] = c[i] + c[i-1];
}
// 临时存放排好序的数据
int r[n] = {0};
// 倒序遍历数组，将元素放入正确的位置
for (int i = n-1; i >= 0; i--)
{
r[c[data[i]] - 1] = data[i];
c[data[i]]--;
}
for (int i = 0; i < n; i++)
{
data[i] = r[i];
}
}
2.2. 计数排序的适用范围
-
计数排序只适用于数据范围不大的场景中，如果数据范围
-
计数排序能给非负整数排序，如果数据是其他类型的，需要将其在不改变相对大小的情况下，转化为非负整数。比如数据有一位小数，我们需要将数据都乘以 10；数据范围为 [-1000, 1000]，我们需要对每个数据加 1000。
3. 基数排序（Radix Sort）？
假设要对 10 万个手机号码进行排序，显然桶排序和计数排序都不太适合，那怎样才能做到时间复杂度为
1.1. 基数排序原理
-
手机号码有这样的规律，假设要比较两个手机号码
的大小，如果在前面几位中，
手机号码已经比
大了，那后面几位就不用看了。
-
借助稳定排序算法，我们可以这么实现。从手机号码的最后一位开始，分别按照每一位的数字对手机号码进行排序，依次往前进行，经过 11 次排序之后，手机号码就都有序了。
-
下面是一个字符串的排序实例，和手机号码类似。
基数排序
-
根据每一位的排序，我们可以用刚才的桶排序或者计数排序来实现，它们的时间复杂度可以做到
，当
-
有时候，要排序的数据并不都是等长的，比如我们要对英文单词进行排序。这时候，我们可以把所有单词都补足到相同长度，位数不够的在后面补 ’0‘，所有字母的 ASCII 码都大于 ‘0’，因此不会影响原有的大小顺序。
-
基数排序需要数据可以分割出独立的位出来，而且位之间有递进的关系。除此之外，每一位的数据范围都不能太大，要可以用线性排序算法来进行排序。
获取更多精彩，请关注「seniusen」!
seniusen
