桶排序，计数排序，基数排序

一、线性排序算法介绍

1. 线性排序算法包括桶排序、计数排序、基数排序。

2. 线性排序算法的时间复杂度为 O(n)。

3. 此 3 种排序算法都不涉及元素之间的比较操作，是非基于比较的排序算法。

4. 对排序数据的要求很苛刻，重点掌握此 3 种排序算法的适用场景。

二、桶排序（Bucket sort）

1. 算法原理：

1. 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序。

2. 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

1. 使用条件

1. 要排序的数据需要很容易就能划分成 m 个桶，并且桶与桶之间有着天然的大小顺序。

2. 数据在各个桶之间分布是均匀的。

1. 适用场景

1. 桶排序比较适合用在外部排序中。

2. 外部排序就是数据存储在外部磁盘且数据量大，但内存有限无法将整个数据全部加载到内存中。

1. 应用案例

1. 需求描述：

有 10GB 的订单数据，需按订单金额（假设金额都是正整数）进行排序但内存有限，仅几百 MB

2. 解决思路：

• 扫描一遍文件，看订单金额所处数据范围，比如 1 元-10 万元，那么就分 100 个桶。

• 第一个桶存储金额 1-1000 元之内的订单，第二个桶存 1001-2000 元之内的订单，依次类推。

• 每个桶对应一个文件，并按照金额范围的大小顺序编号命名（00，01，02，…，99）。

• 将 100 个小文件依次放入内存并用快排排序。

• 所有文件排好序后，只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。

3. 注意点：若单个文件无法全部载入内存，则针对该文件继续按照前面的思路进行处理即可。

三、计数排序（Counting sort）

1. 算法原理

1. 计数其实就是桶排序的一种特殊情况。

2. 当要排序的 n 个数据所处范围并不大时，比如最大值为 k，则分成 k 个桶

3. 每个桶内的数据值都是相同的，就省掉了桶内排序的时间。

1. 案例分析：

假设只有 8 个考生分数在 0-5 分之间，成绩存于数组 A[8] = [2，5，3，0，2，3，0，3]。

使用大小为 6 的数组 C[6]表示桶，下标对应分数，即 0，1，2，3，4，5。

C[6]存储的是考生人数，只需遍历一边考生分数，就可以得到 C[6] = [2，0，2，3，0，1]。

对 C[6]数组顺序求和则 C[6]=[2，2，4，7，7，8]，c[k]存储的是小于等于分数 k 的考生个数。

数组 R[8] = [0，0，2，2，3，3，3，5]存储考生名次。那么如何得到 R[8]的呢？

从后到前依次扫描数组 A，比如扫描到 3 时，可以从数组 C 中取出下标为 3 的值 7，也就是说，到目前为止，包括自己在内，分数小于等于 3 的考生有 7 个，也就是说 3 是数组 R 的第 7 个元素（也就是数组 R 中下标为 6 的位置）。当 3 放入数组 R 后，小于等于 3 的元素就剩下 6 个了，相应的 C[3]要减 1 变成 6。

以此类推，当扫描到第二个分数为 3 的考生时，就会把它放入数组 R 中第 6 个元素的位置（也就是下标为 5 的位置）。当扫描完数组 A 后，数组 R 内的数据就是按照分数从小到大排列的了。

使用条件

1. 只能用在数据范围不大的场景中，若数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序；

2. 计数排序只能给非负整数排序，其他类型需要在不改变相对大小情况下，转换为非负整数；

3. 比如如果考试成绩精确到小数后一位，就需要将所有分数乘以 10，转换为整数。

四、基数排序（Radix sort）

1. 算法原理（以排序 10 万个手机号为例来说明）

1. 比较两个手机号码 a，b 的大小，如果在前面几位中 a 已经比 b 大了，那后面几位就不用看了。

2. 借助稳定排序算法的思想，可以先按照最后一位来排序手机号码，然后再按照倒数第二位来重新排序，以此类推，最后按照第一个位重新排序。

3. 经过 11 次排序后，手机号码就变为有序的了。

4. 每次排序有序数据范围较小，可以使用桶排序或计数排序来完成。

1. 使用条件

1. 要求数据可以分割独立的“位”来比较；

2. 位之间由递进关系，如果 a 数据的高位比 b 数据大，那么剩下的地位就不用比较了；

3. 每一位的数据范围不能太大，要可以用线性排序，否则基数排序的时间复杂度无法做到 O(n)。