桶排序、计数排序源码和性能分析

ゞ浴缸里的玫瑰 2023-06-19 06:51 56阅读 0赞

## 桶排序 ##

quickSort.php文件源码在[《归并排序、快速排序源码和性能分析》][Link 1]的快排部分。

<?php
    /** * 桶排序 * * 1. 根据数据范围确定桶的个数 * 2. 将各个元素放入桶中 * 3.1. 如果桶中的元素未超过最大值限制，则进行排序 * 3.2. 如果桶中的元素超过了最大值限制，则对这个桶的元素再递归进行桶排序 * 4. 将每个桶的元素合并即可得到有序元素 */
    
    require_once './quickSort.php';
    
    define("BUCKET_MAX_CAP", 5); //每个桶的最大容量
    
    /** * @param array $arr * @return array */
    function bucketSort(array $arr) { 
        $arrLength = count($arr);
        if($arrLength <= 1) { 
            return $arr;
        }
    
        $min = min($arr);
        $max = max($arr);
        $buckets = []; //桶
        $result = [];  //每个桶元素合并之后的结果
    
        //计算一共需要多少个桶
        $bucketNumber = ceil(($max-$min)/$arrLength) + 1;
    
        //把所有元素放入桶中
        foreach($arr as $key=>$value) { 
            //计算该元素在桶中的下标
            $bucketIndex = ceil(($value-$min)/$arrLength);
            $buckets[$bucketIndex][] = $value;
        }
    
        for($i=0; $i<$bucketNumber; $i++) { 
            $bucket = $buckets[$i];
            //当前桶的元素个数
            $currentBucketLen = count($bucket);
    
            //如果桶为空，则跳过
            if(0 == $currentBucketLen) { 
                continue;
            }
            //如果桶的元素个数超过最大值，则递归
            if($currentBucketLen > BUCKET_MAX_CAP) { 
                $sorted = bucketSort($bucket);
            }else{ 
                //对桶内元素进行快排
                $sorted = quickSort($bucket);
            }
    
            $result = array_merge($result, $sorted);
        }
        return $result;
    }

测试数据：

$arr = [];
    $arr = [1];
    $arr = [2, 1];
    $arr = [11,23,45,67,88,99,22,34,56,78,90,12,34,5,6,91,92,93,93,94,95,94,95,96,97,98,99,100,0];
    $arr = [0,-1,-4,3];
    
    print_r(bucketSort($arr));

**最好、平均时间复杂度为O(n)**

如果要排序的数据有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)。

**最坏时间复杂度为O(nlogn)**

极端情况下，所有的元素都分配到一个桶中，时间复杂度就退化为O(nlogn)。

**稳定性**

桶排序是否稳定取决于桶内排序算法和元素是如何放入桶中的，首先桶内排序使用稳定的快排算法，而且计算元素在桶中的下标公式为：`$bucketIndex = ceil(($value-$min)/$arrLength);`，因此，桶排序是**稳定的**算法。

**桶排序比较适合用在外部排序中**。  
外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。  
加入有10GB的订单信息，需要按照金额（最大10万元，最小1元）排序，而内存只有几百兆。可以将订单根据金额划分到100个桶中，分别存1 ~ 1000,1001 ~ 2000…的数据。但是我们会发现前几个桶的数据比后几个桶的数据量要大很多，因此我们还需要设置一个桶的上限，当超过这个上限时，就再次递归将这个桶划分为更小的桶。

## 计数排序 ##

再用PHP写这个算法的时候，应该注意一个点，就是我们向数组中插入数据，期望这个数组为 ：  
Array  
(  
\[0\] => 1  
\[1\] => 4  
\[2\] => 6  
\[3\] => 7  
)  
但实际上得到的是：  
Array  
(  
\[0\] => 1  
\[2\] => 6  
\[3\] => 7  
\[1\] => 4  
)  
这是因为我们插入的顺序不是按照数组下标递增（如先插入a\[10\]，再插入a\[1\]）的时候，数组会变为哈希数组，这个概念在[《PHP数组源码解读和底层实现分析》][PHP]中讲解过。

因此，下面遍历bucket数组的时候，用的是for循环而不是foreach。

<?php
    /** * 计数排序 * 假设原数据datas=[0,1,2,1,2,1]，最大值为2 * 1. 遍历datas初始化bucket * 2. bucket数组下标值代表原数据数值，bucket数组中的元素代表原数据值为该下标值的数据个数，如bucket[0]=1代表datas中值为0的元素有1个 * 3. 做这样的操作：设sortedDatas为datas排序后的数组，则bucket=[1,3,2]，将原数据值等于0的数据个数放入bucket[0]，原数据值小于等于1的数据个数放入bucket[1]，原数据值小于等于2的数据个数放入bucket[2]，得到新的bucket=[1,4,6] * 4. 从后往前遍历bucket，例如取datas[5]的时候，从bucket中可以得到小于等于1的数据一共有4个，则这个1在sortedDatas中的下标就应该是3，然后bucket[1] = bucket[1] - 1 代表剩下的datas中小于等于1的数据还有3个 * 5. 由于得到sortedDatas是哈希数组，因此for循环遍历sortedDatas数组得到有序的索引数组 */
    
    function countingSort(array $arr) { 
        $arrLength = count($arr);
        if($arrLength <= 1) { 
            return $arr;
        }
    
        $max = max($arr);
        $bucket = [];       //桶
        $temp = [];
        $sortedDatas = [];  //有序数组
    
        //将arr元素放入桶中
        foreach($arr as $key=>$value) { 
            if(! isset($bucket[$value])) { 
                $bucket[$value] = 1;
            }else{ 
                $bucket[$value]++;
            }
        }
    
        //$index为$bucket第一个值的下标
        for($i = 0; $i <= $max; $i++){ 
            if(isset($bucket[$i])) { 
                $index = $i;
                break;
            }
        }
    
        //遍历bucket
        for($i = $index+1; $i <= $max; $i++){ 
            if(isset($bucket[$i])) { 
                $bucket[$i] += $bucket[$index];
                $index = $i;
            }
        }
    
        //倒序遍历arr
        for($i=$arrLength-1; $i >= 0; $i--) { 
            $data = $arr[$i];
            $number = $bucket[$data];
            $temp[$number-1] = $data;
            $bucket[$data]--;
        }
    
        //遍历temp数组，因为temp数组可能是键值数组：
        // Array
        // (
        // [0] => 1
        // [2] => 6
        // [3] => 7
        // [1] => 4
        // )
        for($i=0; $i < $arrLength; $i++) { 
            $sortedDatas[] = $temp[$i];
        }
    
        return $sortedDatas;
    }

计数排序是桶排序的一个特殊情况，适合数据量大，但是范围小的数据，比如最大值是k，那就可以把这k个数据放入一个长度为k+1的桶中，省去了桶内排序。  
由于计数排序用到了数组下标值代表数据值，所以数据只能是非负整数，如果存在负数，如-100到100的数据，可以给每个数据加100变为0到200范围的数据排序。

**时间复杂度为O(n+k)，k为数据范围**

**稳定性**  
倒序遍历原数据数组的时候，以datas=\[0,1,2,1,2,1\]为例，最后一个1先遍历到，取到的bucke\[1\]就是该值在有序数组中的下标，然后bucket\[1\]减1，下一次遇到1的时候，再取bucket\[1\]肯定就比之前插入的1的下标要小。因此该算法是**稳定的**。

## 应用 ##

其实这两种算法的应用不是非常广泛，虽然他们的平均时间复杂度为O(n)，但是对数据的要求很严格，都是针对**范围不大**的数据才能达到O(n)时间复杂度。

计数排序还要求数据非负，否则还要做额外处理。  
桶排序要求数据分布相对均匀，虽然可以控制一个桶中元素的上限，但是递归的调用会导致空间开销。

计数排序用在类似考生成绩排名或者人口年龄排名上就有很大优势，因为考分或者年龄都是一个小范围数据，用一个桶就可以记录下所有的数据分布情况。

[Link 1]: https://blog.csdn.net/IT_10/article/details/103334997
[PHP]: https://blog.csdn.net/IT_10/article/details/94665305