这一篇我们来看三种时间复杂度为O(n)的排序算法：桶排序、计数排序、基数排序。我们把这类时间复杂度为O(n)的排序算法叫做线性排序。这类排序算法之所以能够做到线性时间，其实是因为它们都不是基于比较来实现排序的。
1. 桶排序 1.1 什么是桶排序
桶排序的基本思想就是将数据拆分到多个有大小区分的桶里面，然后分别对每个桶里面的数据进行排序，完成每个桶里面的数据的排序之后，按照桶与桶之间的数据的大小关系，依次合并数据就得到了所要的有序序列


文章图片
桶排序过程示意图 1.2 桶排序的性能分析
假设我们要将n条数据进行排序，如果我们有m个桶，我们把这n条数据均匀的划分到这m个桶里面，每个桶里的数据就是k=n/m。然后我们对每个桶使用快速排序进行排序，时间复杂度就是O(klogk)。m个桶总的时间复杂度就是O(mklogk)。因为k=n/m。所以整个事件复杂度就是O(nlog(n/m))。当m接近n的时候，log(n/m)就是一个非常小的常数，整个桶排序的时间复杂度就接近O(n)。
它的空间复杂度O(n)，但是并不是需要两倍的数据内存才能进行排序，因为排序过程中存储的只是实际数据的索引
桶内排序时选用稳定排序算法，则它就能做到稳定排序
1.3 桶排序对数据的特殊要求
桶排序看起来很快，但是要达到O(n)的时间复杂度，它对待排序的数据是有要求的

1. 首先，待排序的数据需要能很容易的划分成m个桶，并且桶与桶之间要有天然的大小关系。
2. 其次，数据在各个桶之间的分布要是比较均匀的。如果数据经过划分之后，有些桶里面的数据非常多，有些非常少，那桶内排序的时间复杂度就不是常量级的。极端情况下，如果数据全部在一个桶里面的话，算法的复杂度就退化成了O(nlogn)

1.4 桶排序的算法实现
桶排序的实现思路

1. 根据数据范围和预估的桶的数据容量计算桶的个数，申请桶空间
2. 将待排序的数据划分到各个桶中
3. 对每个桶进行排序
4. 合并排序之后的桶中的数据

完整代码如下

public static void sort(int[] array, int bucketSize) { if (array == null || array.length < 2) { return; } //计算用多少个桶来装数据 int min = array[0]; int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] < min) { min = array[i]; } else if (array[i] > max) { max = array[i]; } } System.out.println("min:" + min); System.out.println("max:" + max); int bucketCount = (max - min) / bucketSize + 1; System.out.println("bucketCount:" + bucketCount); //申请桶空间 int[][] buckets = new int[bucketCount][bucketSize]; int[] indexArray = new int[bucketCount]; //将数据装入桶里面 for (int i = 0; i < array.length; i++) { int bucketIndex = (array[i] - min) / bucketSize; if (indexArray[bucketIndex] == buckets[bucketIndex].length) {// buckets[bucketIndex]满了，需要扩容 ensureCapacity(buckets, bucketIndex); } buckets[bucketIndex][indexArray[bucketIndex]] = array[i]; indexArray[bucketIndex]++; } //对每个桶进行排序 int k = 0; for (int i = 0; i < bucketCount; i++) { sort(buckets[i], 0, indexArray[i] - 1); //合并桶中的数据 for (int j = 0; j < indexArray[i]; j++) { array[k++] = buckets[i][j]; } } }private static void sort(int[] a, int left, int right) { if (left < right) { int low = left; int hight = right; int pivot = a[low]; //找到分区点的位置 while (low < hight) {//有元素之间的位置交换，所以不是稳定排序 while (low < hight && a[hight] >= pivot) { hight--; } a[low] = a[hight]; while (low < hight && a[low] <= pivot) { low++; } a[hight] = a[low]; } a[low] = pivot; //对左右两个分区进行排序 if (left + 1 < low) { sort(a, left, low - 1); } if (right - 1 > low) { sort(a, low + 1, right); } } }private static void ensureCapacity(int[][] buckets, int bucketIndex) { int[] tempArr = buckets[bucketIndex]; int[] newArr = new int[tempArr.length * 2]; for (int j = 0; j < tempArr.length; j++) { newArr[j] = tempArr[j]; } buckets[bucketIndex] = newArr; }

1.5 桶排序的实际应用
桶排序比较适合用在外部排序中。比如说有10GB的订单数据需要按照订单金额进行排序，但是能够使用的内容只有1GB，没有办法一次把所有数据都加载到内存中来，这个时候就可以使用桶排序
具体怎么做呢？

1. 先扫描一遍记录，查看订单金额的数据范围。假设订单的金额范围是1-10万元，我们可以把数据划分到100个桶里面，第一个桶存储1元-1000元之间的订单，第二个桶存储1001-2000之间的订单，依次内推。
2. 然后我们再次遍历订单记录，开始加载我们第一个桶需要的数据进行排序，排好序之后写入到编号为001的桶中。然后在加载第二个桶的数据排序，依次类推。
3. 待所有桶中的数据都排序好了之后，依次读取这排序好的100个文件中的订单数据，写入到一个文件中，这样文件中存储的就是金额从小到大排序的订单数据了

如果某个桶的数据规模过大，依然无法用1GB的内存排序如何处理？

再次对这个桶中的数据进行拆分处理。比如订单在1-1000元的记录特别多，我们可以继续将它划分为1-100,101-200，……901-1000。然后以同样的方式去排序

什么是外部排序

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

1.6 简单示例
使用桶排序给交易记录按照价格来进行排序，我们把加一记录简化成只有价格和编号id的方式
交易记录

public static class Record { private int money; private String id; ... }

桶排序算法

public static void sort(Record[] array, int bucketSize) { if (array == null || array.length < 2) { return; } //计算用多少个桶来装数据 int min = array[0].money; int max = array[0].money; for (int i = 1; i < array.length; i++) { if (array[i].money < min) { min = array[i].money; } else if (array[i].money > max) { max = array[i].money; } } System.out.println("min:" + min); System.out.println("max:" + max); int bucketCount = (max - min) / bucketSize + 1; System.out.println("bucketCount:" + bucketCount); //申请桶空间 Record[][] buckets = new Record[bucketCount][bucketSize]; int[] indexArray = new int[bucketCount]; //将数据装入桶里面 for (int i = 0; i < array.length; i++) { int bucketIndex = (array[i].money - min) / bucketSize; if (indexArray[bucketIndex] == buckets[bucketIndex].length) {// buckets[bucketIndex]满了，需要扩容 ensureCapacity(buckets, bucketIndex); } buckets[bucketIndex][indexArray[bucketIndex]] = array[i]; indexArray[bucketIndex]++; } //对每个桶进行排序 int k = 0; for (int i = 0; i < bucketCount; i++) { //sort(buckets[i], 0, indexArray[i] - 1); //快排，不稳定 sort2(buckets[i], indexArray[i]); //冒泡，稳定排序 //合并桶中的数据 for (int j = 0; j < indexArray[i]; j++) { array[k++] = buckets[i][j]; } } }/** * 冒泡 * * @param array */ private static void sort2(Record[] array, int size) { if (array == null || array.length == 1) { return; } for (int i = 0; i < size; i++) { boolean isExchanged = false; for (int j = 0; j < size - i - 1; j++) {//这里的i表示经过了几次冒泡排序了，经过一次有在最后面多了一位已经排好序的元素，所以下一次要比较的范围也较少1 if (array[j].money > array[j + 1].money) {//只有在后面的元素大于前面的元素的时候才交互，可以保证排序的稳定性 Record temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; isExchanged = true; } } if (!isExchanged) {//当某一趟冒泡排序中没有交换发送的时候，说明序列已经有序了 break; } } }

这里我们注意使用稳定排序来做桶内排序，保证排序的稳定性
测试用例

@Test public void test() { int size = 10; BucketSortRecord.Record[] array = new BucketSortRecord.Record[size]; for (int i = 0; i < size; i++) { BucketSortRecord.Record person = new BucketSortRecord.Record(); person.setMoney(10 + new Random().nextInt(size)); person.setId("record_" + i); array[i] = person; } print(array, "org:"); BucketSortRecord.sort(array, 2); print(array, "sorted:"); }

测试结果

org:{money=13, name='record_0'},{money=14, name='record_1'},{money=14, name='record_2'},{money=12, name='record_3'},{money=14, name='record_4'}, sorted:{money=12, name='record_3'},{money=13, name='record_0'},{money=14, name='record_1'},{money=14, name='record_2'},{money=14, name='record_4'},

我们可以看到排序结果是稳定的
2. 计数排序 2.1 什么是计数排序
计数排序可以看做一种特殊的桶排序，每个桶里面的数据都是相同的，也就不用进行同类排序了。当我们要对n个数据进行排序的时候，我们先计算一下它的数据区间，比如最小值是1，最大值是K，则数据区间就是看，然后将这些数据拆分到这k个桶里面，由于每个桶里面的数据都是相同的，所以我们不用进行桶内排序，拆分完成之后，我们再次遍历每个桶，合并数据就得到了要排序的有序序列


文章图片
计数排序过程示意图 2.2 计算排序的性能分析
计算排序在桶排序的基础上省去了桶内排序，所以它的时间复杂度就是O(n)
它的空间复杂度O(n)
它是稳定排序
2.3 计数排序对数据的特殊要求
计数排序只能用在数据范围不大的场景中，如果数据范围K很大，就不适合使用计数排序了。因为它需要申请与范围同样大小的空间来进行计数，范围太大，内存就可能不够了。
2.4 计数排序的算法实现
计数排序算法实现思路

1. 计算数据之间的区间，申请计数数组
2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置
3. 计算计数数组中元素在将来排好序的序列中的位置
4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置

算法实现

public static void sort(int[] array) { /** * 计数排序的的步骤 * 1. 计算数据之间的区间，申请计数数组 * 2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置 * 3. 计算计算数组中元素在将来排好序的序列中的位置 * 4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置 */ if (array == null || array.length < 2) { return; } //1. 计算数据分别的区间，申请计数数组 int min = array[0]; int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] < min) { min = array[i]; } else if (array[i] > max) { max = array[i]; } } System.out.println("min:" + min); System.out.println("max:" + max); int interval = max - min; System.out.println("interval:" + interval); int[] c = new int[interval + 1]; //2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置 for (int i = 0; i < array.length; i++) { c[array[i] - min]++; } //3. 计算计算数组中元素在将来排好序的序列中的位置 for (int i = 1; i < c.length; i++) { c[i] = c[i - 1] + c[i]; } //4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置 int[] temp = new int[array.length]; for (int i = array.length - 1; i >= 0; i--) {//倒序保证稳定性 int index = c[array[i] - min] - 1; temp[index] = array[i]; c[array[i] - min]--; } for (int i = array.length - 1; i >= 0; i--) { array[i] = temp[i]; } }

2.5 计数排序的实际应用
计数排序可以应用在考试成绩的排名上，比如高考成绩的快速排名。
假如高考总分是900分，最小分时0分，总共有50万名考生，我们就可以将这些学生划分到901个桶里面，由于桶里面的分数相同，所以不同再进行排序，我们只要一次扫描每个桶，将桶内的考生依次输出到一个数组中，就能实现对50万名考生的成绩的排序了。
2.6 简单实例
我们简单的实现一些对考生成绩的排序，这里我们将考生信息简化成只有总成绩和名字两个部分
考生信息

public static class Person { private int age; private String name; ... }

计数排序算法

public static void sort(Person[] array) { /** * 计数排序的的步骤 * 1. 计算数据分别的区间，申请计数数组 * 2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置 * 3. 计算计算数组中元素在将来排好序的序列中的位置 * 4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置 */ if (array == null || array.length < 2) { return; } //1. 计算数据分别的区间，申请计数数组 int min = array[0].age; int max = array[0].age; for (int i = 1; i < array.length; i++) { if (array[i].age < min) { min = array[i].age; } else if (array[i].age > max) { max = array[i].age; } } System.out.println("min:" + min); System.out.println("max:" + max); int interval = max - min; System.out.println("interval:" + interval); int[] c = new int[interval + 1]; //2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置 for (int i = 0; i < array.length; i++) { c[array[i].age - min]++; } //3. 计算计算数组中元素在将来排好序的序列中的位置 for (int i = 1; i < c.length; i++) { c[i] = c[i - 1] + c[i]; } //4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置 Person[] temp = new Person[array.length]; for (int i = array.length - 1; i >= 0; i--) { int index = c[array[i].age - min] - 1; temp[index] = array[i]; c[array[i].age - min]--; } for (int i = array.length - 1; i >= 0; i--) { array[i] = temp[i]; } }

测试代码

@Test public void test() { int size = 5; CountingSortPerson.Person[] array = new CountingSortPerson.Person[size]; for (int i = 0; i < size; i++) { CountingSortPerson.Person person = new CountingSortPerson.Person(); person.setAge(10 + new Random().nextInt(5)); person.setName("name_" + i); array[i] = person; } print(array, "org:"); CountingSortPerson.sort(array); print(array, "sorted:"); }

测试结果

org:{age=10, name='name_0'},{age=13, name='name_1'},{age=12, name='name_2'},{age=11, name='name_3'},{age=11, name='name_4'}, sorted:{age=10, name='name_0'},{age=11, name='name_3'},{age=11, name='name_4'},{age=12, name='name_2'},{age=13, name='name_1'},

3. 基数排序 3.1 什么是基数排序
基数排序是一种多关键字的排序算法，其中每个关键字可以使用线性排序算法来完成排序，通过依次对每个关键字进行排序之后，就得到了要的有序序列。这里要求每个关键字使用的线性排序要能保证稳定性。

文章图片
基数排序过程示意图 3.2 基数排序的性能分析
基数排序使用其他线性排序来完成关键字的排序，所以它的时间复杂度也是O(n)，空间复杂度O(n)，它是稳定排序
3.3 基数排序对数据的特殊要求
基数排序对数据的要求:

1. 待排序的数据必须能够分割成多个关键字来比较，且关键字之间有递进关系，比如a的高位比b的高位大，则a必定大于b。
2. 关键字的范围不能太大，要可以使用线性排序算法来排序。

3.4 基数排序的算法实现
这里直接编写一个对手机号码进行排序的算法
算法实现思路

1. 拆分关键字
2. 分别对每个关键字进行线性排序

代码实现

public static void sort(int[] array) { // 从个位开始，对数组arr按"指数"进行排序 for (int exp = 1; array[0] / exp > 0; exp *= 10) { countingSort(array, exp); } }private static void countingSort(int[] array, int exp) { if (array == null || array.length < 2) { return; } //1. 计算数据分别的区间，申请计数数组 int[] c = new int[10]; //2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置 for (int i = 0; i < array.length; i++) { c[(array[i] / exp) % 10]++; } //3. 计算计算数组中元素在将来排好序的序列中的位置 for (int i = 1; i < c.length; i++) { c[i] = c[i - 1] + c[i]; } //4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置 int[] temp = new int[array.length]; for (int i = array.length - 1; i >= 0; i--) {//倒序保证稳定性 int cindex = (array[i] / exp) % 10; temp[c[cindex] - 1] = array[i]; c[cindex]--; } for (int i = array.length - 1; i >= 0; i--) { array[i] = temp[i]; } }

测试用例

@Test public void test1() { int size = 10; int[] array = new int[size]; int[] array2 = new int[size]; for (int i = 0; i < size; i++) { int num = 1; for (int j = 0; j < 5; j++) { num = num * 10 + new Random().nextInt(10); } array[i] = num; array2[i] = num; } print(array, "org:"); print(array2, "org:"); RadixSort.sort(array); MergeSort.sort(array2); print(array, "sorted:"); print(array2, "sorted:"); }

测试结果

org:186402,159502,111311,107840,111943,191059,181161,147774,143482,199457, org:186402,159502,111311,107840,111943,191059,181161,147774,143482,199457, sorted:107840,111311,111943,143482,147774,159502,181161,186402,191059,199457, sorted:107840,111311,111943,143482,147774,159502,181161,186402,191059,199457,

这里我们采用归并排序来做一个结果对比，验证排序的正确性
3.5 基数排序的实际应用
基数排序还可以用在单词的排序中等场景
源码 完整源码和测试用例，请查看github之排序

1. 桶排序：BucketSort.java、BucketSortTest.java、BucketSortRecord.java、BucketSortRecordTest.java
2. 计数排序：CountingSort.java、CountingSortTest.java、CountingSortPerson.java、CountingSortPersonTest.java
3. 基数排序：RadixSort.java、RadixSortTest.java

说明 【排序三（桶排序、计数排序、基数排序）】算法示意图来源：算法动画演示网站

推荐阅读

• 

  孩子|孩子打喷嚏的6大诱因，最后一个要警惕！
• 

  社区服务中心上班好吗
• 

  360护眼模式怎么打开,新版360护眼模式怎么没有了
• 

  驾校一点通模拟题_驾校一点通模拟的准吗
• 

  小鹏汽车g3首付多少 小鹏汽车g3首付多少万
• 

  怎么腌辣椒好吃又简单 腌辣椒好吃又简单的做法与步骤
• 

  立体显微镜,超景深三维立体显微镜
• 

  pdm需求分析,PDM分析
• 

  板栗汤怎么煲
• 

  详解打印机清零操作方法 爱普生l358废墨清零步骤
• 

  20180526
• 

  跨经度最多的大洲和大洋分别是什么
• 

  开源软件FFmpeg的使用
• 

  小儿过敏性鼻炎咳嗽怎么办
• 

  有哪些NBA球员在新秀第一年就成为球队老大的？
• 

  三国演义主要内容介绍 三国演义主要内容概括
• 

  糖尿病|服用达格列净，别忘了定期检查尿常规，孙医生说这种检查很重要
• 

  月亮上的兔子叫什么名字
• 

  痘痘肌可以用免洗面膜吗
• 

  腌萝卜要不用放水

• 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
• 一个人的旅行，三亚
• 2018-02-06第三天|2018-02-06第三天 不能再了，反思到位就差改变
• 第三节|第三节 快乐和幸福（12）
• android第三方框架（五）ButterKnife
• 遇到一哭二闹三打滚的孩子，怎么办┃山伯教育
• 第326天
• 三十年后的广场舞大爷
• 一百二十三夜，请嫁给我
• 2018年9月5日，星期三，天气晴