计算与数据结构篇 - 排序(桶排序)

排序是一个特别常见的问题，也是算法与数据结构中绕不开的话题，有次去小米，面试官问我这样一个场景，每周四10点是小米开放日，在一段时间内，会涌进2kw的数据流，怎么排序，当时会有订单状态？

桶排序、计数排序、基数排序以上这三种排序算法是适用于某个特别的场景。

桶排序（Bucket sort）

核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶里就有 k=n/m 个元素。每个桶内部使用快速排序，时间复杂度为 O(k * logk)。m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。当桶的个数 m 接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

桶排序对特殊场景是有要求的，

• 要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。

• 数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？

我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02…99）。

不过，你可能也发现了，订单按照金额在 1 元到 10 万元之间并不一定是均匀分布的 ，所以 10GB 订单数据是无法均匀地被划分到 100 个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢？

针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在 1 元到 1000 元之间的比较多，我们就将这个区间继续划分为 10 个小区间，1 元到 100 元，101 元到 200 元，201 元到 300 元…901 元到 1000 元。如果划分之后，101 元到 200 元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。

/**
 * 第一种桶排序的办法，每个桶存储相同值的数据
 **/

function bucketSort($nonSortArray){
    //选出桶中最大值和最小值
    $min = min($nonSortArray);
    $max = max($nonSortArray);
     
    //生成桶,默认每个桶中数据只有0个
    $bucket = array_fill($min, $max-$min+1, 0);
     
    //数据入桶
    foreach ($nonSortArray as $value){
        $bucket[$value]++;//对应桶的个数计增
    }
     
    //数据出桶
    $sortArray = array();  
    foreach ($bucket as $k=>$v){
        for($i=1;$i<=$v;$i++){
            //每个桶中的数据个数
            $sortArray[]=$k;
        }
    }
    return $sortArray;
}

计数排序（Counting sort）

计数排序其实是桶排序的一种特殊情况。 当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。

我们都经历过高考，高考查分数系统你还记得吗？我们查分数的时候，系统会显示我们的成绩以及所在省的排名。如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次呢？

考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。

考生的满分是 900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。

function countingSort($arr) {

        $length = count($arr);
        if($length <= 1) return $arr;

        $size = count($arr);
        $max = $arr[0];

        //找出数组中最大的数
        for($i=1;$i<$size;$i++) {
            if($max < $arr[$i]) $max = $arr[$i];
        }

        //初始化用来计数的数组
        for ($i=0;$i<=$max;$i++) {
            $count_arr[$i] = 0;
        }

        //对计数数组中键值等于$arr[$i]的加1
        for($i=0;$i<$size;$i++) {
            $count_arr[$arr[$i]]++;
        }

        //相邻的两个值相加
        for($i=1;$i<=$max;$i++) {
            $count_arr[$i] = $count_arr[$i-1] + $count_arr[$i];
        }

        //键与值翻转
        for ($i=$size-1;$i>=0;$i--) {
            $over_turn[$count_arr[$arr[$i]]] = $arr[$i];
            $count_arr[$arr[$i]]--; // 前一个数找到位置后，那么和它值相同的数位置往前一步
        }

        //按照顺序排列
        $result = array();
        for ($i=1;$i<=$size;$i++) {
            array_push($result,$over_turn[$i]);
        }

        return $result;
    }