共计 3410 个字符，预计需要花费 9 分钟才能阅读完成。
后面「码哥字节」介绍了一些经典排序算法，它们的工夫复杂度最好是 O(nlogn)，那 如何把百万级别的订单依据金额排序？是不是感觉能够依照之前学的归并排序、疾速排序实现？性能是能够实现，然而效率太低了。明天「码哥」带大家一起玩转非凡场景下的排序算法，在 O(n) 工夫复杂度的状况下实现排序。
「码哥」带大家学习的算法类比「超跑型赛车」，用于非凡场景能实现飞快速度。快排、归并是经济实用型小轿车。而桶排序、计数排序、基数排序则是赛道上的跑车竞速，也叫做 线性排序。
来不及解释了，快上车！明天先来桶排序压压惊。
桶排序（Bucket Sort）
顾名思义，会应用「桶」，核心思想就是 把要排序的的数据分到几个有序的桶里，每个桶外面的数据在独自进行排序，所有的桶内数据排序实现后，再依照桶的程序顺次取出，组成的序列就是有序的。
为了桶排序的高效，咱们须要做到以下两点：
- 在额定空间短缺的状况下，尽量减少桶的数量。
- 应用的映射函数可能把输出的 n 个数据平均的调配到 k 个桶中。
同时，对于桶内元素的排序，抉择哪一种排序算法对于性能的影响也至关重要。
桶排序的根本思维是：把数组 arr 划分为 n 个大小雷同子区间（桶），每个子区间各自排序，最初合并。
为何说工夫复杂度是 O(n) 呢? 咱们一探到底。
如果待排序的数据有 n 个，咱们须要将其应用函数映射平均的调配到 k 个桶外面，每个桶的元素个数 y = n / k。
接着每个桶的外部应用快排，工夫复杂度就是 O(y logy)，k 个桶排序的工夫复杂度就是 O(k y logy)，因为 y = n / k。所以整个桶排序的工夫复杂度就是 O(n log(n / k))。当桶的个数 k 靠近 数据个数 n，log(n / k) 就是一个很小的常量，桶排序工夫复杂度靠近 O(n)。
看起来如此优良，它能代替码哥之间介绍的 O(nlogn) 复杂度的排序算法么？
很遗憾，答案是否定的。跑车能跑的赛道是非凡的，并不能代替家用小轿车。实际上它的使用场景很刻薄。
- 要排序的数据很容易平均的划分成 k 个桶，并且桶与桶之间有着人造的大小程序。这样才在实现在每个桶内的数据都排序好了当前不须要再进行排序。
- 数据在每个桶之间都是平均的散布，如果呈现有的桶很少数有的很少。那桶内排序的工夫复杂度就不是常量级了，在极其状况下数据都划分到一个桶里，也就进化成 O(nlogn) 的工夫复杂度了。
实用场景
比拟适宜用在内部排序中。所谓的内部排序就是数据存储在内部磁盘中，数据量比拟大而内存无限，无奈一次性全副加载到内存中。
比如说咱们有 10GB 的订单数据，咱们心愿按订单金额（假如金额都是正整数）进行排序，然而咱们的内存无限，只有几百 MB，没方法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？
解决思路
一下，对应依据订单金额把 10G 订单数据排序也是如此，订单金额最小是 1 元，最大是 10 万元。咱们将所有订单依据金额划分到 100 个桶里，第一个桶咱们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且依照金额范畴的大小程序编号命名（00，01，02…99）。
现实的状况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被平均划分到 100 个文件中，每个小文件中存储大概 100MB 的订单数据，咱们就能够将这 100 个小文件顺次放到内存中，用快排来排序。等所有文件都排好序之后，咱们只须要依照文件编号，从小到大顺次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是依照金额从小到大排序的订单数据了。
代码实战
/**
* 桶排序：把数组 arr 划分为 n 个大小雷同子区间（桶），每个子区间各自排序，最初合并
*/
public class BucketSort implements LineSort {private static final QuickSort quickSort = new QuickSort();
@Override
public int[] sort(int[] sourceArray, int bucketSize) {
// 找出最大、最小值
int minValue = sourceArray[0];
int maxValue = sourceArray[1];
for (int value : sourceArray) {minValue = Math.min(minValue, value);
maxValue = Math.max(maxValue, value);
}
// 桶数量
int bucketCount = (maxValue - minValue) / bucketSize + 1;
int[][] buckets = new int[bucketCount][bucketSize];
// 保留每个桶的数组的元素下标，默认值 0
int[] indexArr = new int[bucketCount];
// 将数组中值调配到各个桶里
for (int value : sourceArray) {int bucketIndex = (value - minValue) / bucketSize;
// 以后桶的数组达到最大值, 须要拓容
if (indexArr[bucketIndex] == buckets[bucketIndex].length) {ensureCapacity(buckets, bucketIndex);
}
// 将数据放到桶中，并且桶对应的数组下标 + 1
buckets[bucketIndex][indexArr[bucketIndex]++] = value;
}
// 对每个桶进行排序，这里应用了疾速排序
int k = 0;
for (int i = 0; i < buckets.length; i++) {if (indexArr[i] == 0) {continue;}
// 默认容量是 bucketSize, 要依据理论桶的容量排序，否则有余 bucketSize 的默认值是 0
quickSort.quickSortInternal(buckets[i], 0, indexArr[i] - 1);
for (int j = 0; j < indexArr[i]; j++) {sourceArray[k++] = buckets[i][j];
}
}
return sourceArray;
}
/**
* 数组扩容, 并保留数据
*
* @param buckets
* @param bucketIndex
*/
private 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, 100000]
@DisplayName("线性排序算法测试")
public class LineSortTest {
private static int length = 100;
private int[] array = new int[length];
@BeforeEach
public void beforeEach() {Random rand = new Random();
for (int i = 0; i < length; i++) {// 随机生成 [1, 1000000] 的数据
array[i] = rand.nextInt(length) + 1;
}
}
@DisplayName("桶排序")
@Test
public void testBucketSort() {BucketSort bucketSort = new BucketSort();
// 100 数据，10 个桶
int[] sort = bucketSort.sort(array, 10);
System.out.println(Arrays.toString(sort));
}
}总结
如何依据年龄给 100 万用户排序？当初思考题是不是变得非常简单了呢？我来说一下我的解决思路。
实际上，依据年龄给 100 万用户排序，就相似依照问题给 50 万考生排序。咱们假如年龄的范畴最小 1 岁，最大不超过 120 岁。咱们能够遍历这 100 万用户，依据年龄将其划分到这 120 个桶里，而后顺次程序遍历这 120 个桶中的元素。这样就失去了依照年龄排序的 100 万用户数据。
后盾回复“加群”，退出技术社区一起学习。
