桶排序, 计数排序,基数排序,因为这些排序算法的时间复杂度是线性的, 时间复杂度为 O(n),所以这类排序算法叫做线性排序.
将排序的数据分到几个有序的捅里面,每个桶排序完之后,再把每个桶里的数据按照数据依次取出,组成的序列就是有序的了.
桶排序时间复杂度为 O(n)
桶排序比较适合用在外部排序中。
数据存储在外边磁盘中,数据量比较大,内存有限,无法将数据全部加载到内存中.
按照范围进行拆分,直到拆解的文件可以放到内存中.进行排序操作, 再组合.
当要排序的 n个数据，所处的范围并不大的时候，比如最大值为k,我们可以把数据分为 k 个桶.每个桶内的数据值是相同的,省掉了桶内排序的时间.
假设只有 8 个考生，分数在 0 到 5 分之间。这 8 个考生的成绩我们放在一个数组 A[8] 中，它们分别是：2，5，3，0，2，3，0，3。
考生的成绩从 0 到 5 分，我们使用大小为 6 的数组 C[6] 表示桶，其中下标对应分数。不过，C[6] 内存储的并不是考生，而是对应的考生个数。像我刚刚举的那个例子，我们只需要遍历一遍考生分数，就可以得到 C[6] 的值。
从图中可以看出，分数为 3 分的考生有 3 个，小于 3 分的考生有 4 个，所以，
成绩为 3 分的考生在排序之后的有序数组 R[8] 中，会保存下标 4，5，6 的位置。
那我们如何快速计算出，每个分数的考生在有序数组中对应的存储位置呢？这个处理方法非常巧妙，很不容易想到。
思路是这样的：我们对 C[6] 数组顺序求和，C[6] 存储的数据就变成了下面这样子。C[k] 里存储小于等于分数 k 的考生个数。
有了前面的数据准备之后，现在我就要讲计数排序中最复杂、最难理解的一部分了，请集中精力跟着我的思路！
我们从后到前依次扫描数组 A。比如，当扫描到 3 时，我们可以从数组 C 中取出下标为 3 的值 7，也就是说，到目前为止，包括自己在内，分数小于等于 3 的考生有 7 个，也就是说 3 是数组 R 中的第 7 个元素（也就是数组 R 中下标为 6 的位置）。当 3 放入到数组 R 中后，小于等于 3 的元素就只剩下了 6 个了，所以相应的 C[3] 要减 1，变成 6。
以此类推，当我们扫描到第 2 个分数为 3 的考生的时候，就会把它放入数组 R 中的第 6 个元素的位置（也就是下标为 5 的位置）。当我们扫描完整个数组 A 后，数组 R 内的数据就是按照分数从小到大有序排列的了。
上面的过程有点复杂，我写成了代码，你可以对照着看下。
// 计数排序，a 是数组，n 是数组大小。假设数组中存储的都是非负整数。 public void countingSort(int[] a, int n) { if (n <= 1) return; // 查找数组中数据的范围 int max = a[0]; for (int i = 1; i < n; ++i) { if (max < a[i]) { max = a[i]; } } int[] c = new int[max + 1]; // 申请一个计数数组 c，下标大小 [0,max] for (int i = 0; i <= max; ++i) { c[i] = 0; } // 计算每个元素的个数，放入 c 中 for (int i = 0; i < n; ++i) { c[a[i]]++; } // 依次累加 for (int i = 1; i <= max; ++i) { c[i] = c[i-1] + c[i]; } // 临时数组 r，存储排序之后的结果 int[] r = new int[n]; // 计算排序的关键步骤，有点难理解 for (int i = n - 1; i >= 0; --i) { int index = c[a[i]]-1; r[index] = a[i]; c[a[i]]--; } // 将结果拷贝给 a 数组 for (int i = 0; i < n; ++i) { a[i] = r[i]; } }
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。
而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。
注意，这里按照每位来排序的排序算法要是稳定的，否则这个实现思路就是不正确的。因为如果是非稳定排序算法，那最后一次排序只会考虑最高位的大小顺序，完全不管其他位的大小关系，那么低位的排序就完全没有意义了。
根据每一位来排序，我们可以用刚讲过的桶排序或者计数排序，它们的时间复杂度可以做到 O(n)。如果要排序的数据有 k 位，那我们就需要 k 次桶排序或者计数排序，总的时间复杂度是 O(k*n)。当 k 不大的时候，比如手机号码排序的例子，k 最大就是 11，所以基数排序的时间复杂度就近似于 O(n)。
实际上，有时候要排序的数据并不都是等长的，比如我们排序牛津字典中的 20 万个英文单词，最短的只有 1 个字母，最长的我特意去查了下，有 45 个字母，中文翻译是尘肺病。对于这种不等长的数据，基数排序还适用吗？
实际上，我们可以把所有的单词补齐到相同长度，位数不够的可以在后面补“0”，因为根据ASCII 值，所有字母都大于“0”，所以补“0”不会影响到原有的大小顺序。这样就可以继续用基数排序了。
基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。
除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
总结：
桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。 2.线性排序算法的时间复杂度为O(n)。 3.此3种排序算法都不涉及元素之间的比较操作，是非基于比较的排序算法。 4.对排序数据的要求很苛刻，重点掌握此3种排序算法的适用场景。 二、桶排序（Bucket sort） 1.算法原理： 1）将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序。 2）桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。 2.使用条件 1）要排序的数据需要很容易就能划分成m个桶，并且桶与桶之间有着天然的大小顺序。 2）数据在各个桶之间分布是均匀的。 3.适用场景 1）桶排序比较适合用在外部排序中。 2）外部排序就是数据存储在外部磁盘且数据量大，但内存有限无法将整个数据全部加载到内存中。 4.应用案例 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）每个桶内的数据值都是相同的，就省掉了桶内排序的时间。 2.代码实现（参见下一条留言） 案例分析： 假设只有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内的数据就是按照分数从小到大排列的了。 3.使用条件 1）只能用在数据范围不大的场景中，若数据范围k比要排序的数据n大很多，就不适合用计数排序； 2）计数排序只能给非负整数排序，其他类型需要在不改变相对大小情况下，转换为非负整数； 3）比如如果考试成绩精确到小数后一位，就需要将所有分数乘以10，转换为整数。 四、基数排序（Radix sort） 1.算法原理（以排序10万个手机号为例来说明） 1）比较两个手机号码a，b的大小，如果在前面几位中a已经比b大了，那后面几位就不用看了。 2）借助稳定排序算法的思想，可以先按照最后一位来排序手机号码，然后再按照倒数第二位来重新排序，以此类推，最后按照第一个位重新排序。 3）经过11次排序后，手机号码就变为有序的了。 4）每次排序有序数据范围较小，可以使用桶排序或计数排序来完成。 2.使用条件 1）要求数据可以分割独立的“位”来比较； 2）位之间由递进关系，如果a数据的高位比b数据大，那么剩下的地位就不用比较了； 3）每一位的数据范围不能太大，要可以用线性排序，否则基数排序的时间复杂度无法做到O(n)。
