如何把百万级别的订单根据金额排序

￡神魔★判官ぃ 2022-11-01 04:21 110阅读 0赞

前面「码哥字节」介绍了一些[经典排序算法][Link 1]，它们的时间复杂度最好是 O(nlogn)，那 **如何把百万级别的订单根据金额排序？**是不是觉得可以按照之前学的归并排序、快速排序实现？功能是可以完成，但是效率太低了。今天「码哥」带大家一起玩转特殊场景下的排序算法，在 O(n) 时间复杂度的情况下实现排序。

「码哥」带大家学习的算法类比「超跑型赛车」，用于特殊场景能实现飞快速度。快排、归并是经济实用型小轿车。而桶排序、计数排序、基数排序则是赛道上的跑车竞速，也叫做**线性排序**。

来不及解释了，快上车！今天先来桶排序压压惊。

## 桶排序（Bucket Sort） ##

顾名思义，会使用「桶」，核心思想就是 **把要排序的的数据分到几个有序的桶里，每个桶里面的数据在单独进行排序，所有的桶内数据排序完成后，再按照桶的顺序依次取出，组成的序列就是有序的。**

为了桶排序的高效，我们需要做到以下两点：

1.  在额外空间充足的情况下，尽量增加桶的数量。
2.  使用的映射函数能够把输入的 n 个数据均匀的分配到 k 个桶中。

同时，对于桶内元素的排序，选择哪一种排序算法对于性能的影响也至关重要。

桶排序的基本思想是：`把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并`。

![96795c0e2410ff546358a2f81083960d.png][]

为何说时间复杂度是 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) 复杂度的排序算法么？**

很遗憾，答案是否定的。跑车能跑的赛道是特殊的，并不能代替家用小轿车。实际上它的运用场景很苛刻。

1.  要排序的数据很容易均匀的划分成 k 个桶，并且桶与桶之间有着天然的大小顺序。这样才在实现在每个桶内的数据都排序好了以后不需要再进行排序。
2.  数据在每个桶之间都是均匀的分布，假如出现有的桶很多数有的很少。那桶内排序的时间复杂度就不是常量级了，在极端情况下数据都划分到一个桶里，也就退化成 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 万用户数据。

文章来源：[https://xie.infoq.cn/article/d3ed18cc1d104c962f41d073c][https_xie.infoq.cn_article_d3ed18cc1d104c962f41d073c]

[Link 1]: https://mp.weixin.qq.com/s/JW_46uRGuVhv5FBH77QtvA
[96795c0e2410ff546358a2f81083960d.png]: /images/20221024/d6610f98cfc04d64a4f941e6882e50c7.png
[https_xie.infoq.cn_article_d3ed18cc1d104c962f41d073c]: https://xie.infoq.cn/article/d3ed18cc1d104c962f41d073c