掘金后端 ( ) • 2022-08-05 13:57

本文已参与「新人创作礼」活动，一起开启掘金创作之路。

前言

在上篇文章《十大经典排序算法（动图演示）》中，已经能够了解各种排序算法的思想逻辑，虽然其中提供了代码，但对其解析却并不够全面，而且使用的是js来进行编写演示。本人根据其上代码转换为PHP，并对其代码进行深入解析，并提供相应的优化方法/思路。因此，本文中重点看的不是内容不是代码，而是代码注释。希望能够帮助大家更好地理解各排序算法的编码思路，掌握算法的各种基本方法。

ps: 代码都是可以正确运行的，亲测结果无误

十大排序算法代码的解析及优化

1. 冒泡排序（Bubble Sort）

1.1 原始冒泡排序

//原始冒泡排序方式
function bubbleSort1(array $arr): array
{
    $count = 0;
    //先获取数组总长度，之所以不写在for中，是为了避免重复计算总长度，浪费
    $len = count($arr);
    //外层循环，每执行一次内部循环，最后面的一个数字就将被确定下来，那么执行“数组总长度”次循环，就能够确定所有数字的排序
    for ($i = 0; $i < $len - 1; $i++) {
        //将指针当前两个相邻元素对比排序，排好序后指针后移一位，接着右边两个元素进行排序
        for ($j = 0; $j < $len - 1 - $i; $j++) {
            //$j=$i 是因为后面的内容已经排序过，则不需要再去排序

            // 相邻元素两两对比
            if ($arr[$j] > $arr[$j + 1]) {
                // 元素交换
                $temp = $arr[$j + 1];
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $temp;
            }

            $count++;           //计数用
        }
    }
    echo '循环次数：' . $count . PHP_EOL;
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(bubbleSort1($waitSort));

1.2 优化后的冒泡排序

/*
 * ！！！建议使用这一种
 * 每次排序前或排序后数组的后面都有一部分已经有序
 * 这时我们只要记下最后一次排序的数组的下标
 * 下次排序的时候就可以只排序到此下标位置即可
 * 因为后面的已经有序了
 */
function bubbleSort2(array $arr): array
{
    $count = 0;
    $len = count($arr);
    //外层循环，这里让$i从最末尾开始循环，是为方便下面的边界做处理
    for ($i = $len - 1; $i > 0; $i--) {
        //初始化border，让 border - 1 <= 0 即可
        $border = 1;

        for ($j = 0; $j < $i; $j++) {
            // 相邻元素两两对比
            if ($arr[$j] > $arr[$j + 1]) {
                // 元素交换
                $temp = $arr[$j + 1];
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $temp;

                $border = $j + 1;   //刷新边界，它后面的肯定都是完成排序了的，否则会再次进入这个排序判断中
            }
            $count++;           //计数用
        }

        //更新待排序元素的边界,下一次比较到记录位置即可，可以跳过已经完成的排序
        $i = $border;
    }
    echo '循环次数：' . $count . PHP_EOL;
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(bubbleSort2($waitSort));

1.3 鸡尾酒冒泡排序

/*
 * 面对极端情况会加快，但平常使用没多大必要
 * 鸡尾酒排序等于是冒泡排序的轻微变形
 * 不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素
 * 他可以得到比冒泡排序稍微好一点的性能
 * 原因是冒泡排序只从一个方向进行比对（由低到高），每次循环只移动一个项目；但是，鸡尾酒排序元素比较和交换是双向的
 */
function bubbleSort3(array $arr): array
{
    $count = 0;
    $len = count($arr);
    for ($i = 0; $i < $len / 2; $i++) {
        $flag = false;
        //奇数轮,从左向右比较交换
        for ($j = 0; $j < $len - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
                //此趟排序没有进行数值交换
                $flag = true;
            }
            $count++;
        }

        //在一趟排序中没有发生过交换，代表已经全部排序完成，那么直接终止排序
        if (!$flag) {
            break;
        }

        //偶数轮,从右向左比较交换
        for ($j = $len - 1; $j > $i; $j--) {
            if ($arr[$j] < $arr[$j - 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j - 1];
                $arr[$j - 1] = $temp;
                //此趟排序没有进行数值交换
                $flag = true;
            }
            $count++;
        }
        //在一趟排序中没有发生过交换
        if (!$flag) {
            break;
        }
    }
    echo '循环次数：' . $count . PHP_EOL;
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(bubbleSort3($waitSort));

2. 选择排序（Selection Sort）

2.1 原始选择排序

//原始选择排序
function selectionSort1(array $arr): array
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        //默认当前下标所指元素是最小元素，这里记录元素所在下标
        $minIndex = $i;

        //内部循环，寻找从i+1位置后最小的元素值
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {     // 寻找最小的数
                $minIndex = $j;                 // 将最小数的下标保存
            }
        }

        //交换最小值跟它当前下标元素（外层循环当前下标的元素），交换后，数组从左到右逐步确定排序
        $temp = $arr[$i];
        $arr[$i] = $arr[$minIndex];
        $arr[$minIndex] = $temp;
    }
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(selectionSort1($waitSort));

2.2 左右双路选择排序

//左右双路选择排序
function selectionSort2(array $arr): array
{
    $len = count($arr);
    //通过元素下标交换数组里面元素的位置，这里简单的封成函数
    $exch = function (&$arr, $index1, $index2) {
        $temp = $arr[$index1];
        $arr[$index1] = $arr[$index2];
        $arr[$index2] = $temp;
    };

    //左右双路进行排序，记录分别记录最大值和最小值所在元素下标，当左右都跑完时，排序结束
    for ($left = 0, $right = $len - 1; $left < $right; $left++, $right--) {
        $min = $left;           // 记录最小值
        $max = $right;          // 记录最大值

        //获取中间未确定部分的最大值和最小值
        for ($index = $left; $index <= $right; $index++) {
            if ($arr[$index] < $arr[$min]) {
                $min = $index;
            }
            if ($arr[$max] < $arr[$index]) {
                $max = $index;
            }
        }

        // 将最小值交换到 left 的位置
        $exch($arr, $left, $min);

        //如果最大值和最小值是同一个值，但是上面已经将最小值交换到了left位置上，那么其实要做的，应是把原本left位置的元素(现处于min位置)跟最大值交换位置
        if ($left == $max) {
            $max = $min;
        }
        $exch($arr, $right, $max);
    }
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(selectionSort2($waitSort));

3. 插入排序（Insertion Sort）

3.1 原始插入排序

//插入排序
function insertionSort1($arr)
{
    $len = count($arr);
    //从第二个元素开始循环
    for ($i = 1; $i < $len; $i++) {
        //当前下标元素的上一个元素位置
        $preIndex = $i - 1;
        $current = $arr[$i];    //记录当前元素
        //如果计划插入的位置已经小于0，那么代表已经移动到最左边，该值不能够放置，preIndex没有过任何变动，值其实还是放在原位
        //如果计划插入位置的元素大于当前元素，那么即代表当前元素还可以放到计划插入位置前面，那么便将计划插入位置的元素往后挪一位，留出空间放置插入元素
        //计划插入位置只有小于0或者到最小的可以放置位置时，才结束，那时候的计划插入位置才是真正所要插入元素的位置
        while ($preIndex >= 0 && $arr[$preIndex] > $current) {
            //将原本的位置往后挪一位
            $arr[$preIndex + 1] = $arr[$preIndex];
            //向左查看下一个计划插入的位置
            $preIndex--;
        }
        //将抽取出的元素放置到所要插入的位置
        $arr[$preIndex + 1] = $current;
    }
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(insertionSort1($waitSort));

3.2 折半插入排序

//折半插入排序
//将待排序元素通过二分查找放到已有序的子序列，更快速的定位定位插入的位置
function insertionSort2($arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        //折半查找应该插入的位置
        $left = 0;
        //二分查找范围仅限于已经进行排序的当前下标前数组
        $right = $i - 1;

        //获取当前待插入元素的值
        $temp = $arr[$i];

        while ($left <= $right) { //当左右边界交错时，结束查找
            //获取中间位置
            $m = floor(($left + $right) / 2);
            if ($arr[$m] > $temp) {
                //如果中间值大于查找值，那么代表查找值可插入位置在左边，那么将right边界左移
                $right = $m - 1;
            } else {
                //如果中间值小于查找值，那么代表查找值可插入位置在右边，那么将left边界右移
                $left = $m + 1;
            }
        }
        //$left就是最终可插入数据的位置
        //将right+1位置直至i所在位置，全部向右挪一位
        for ($j = $i; $j > $left; $j--) {
            $arr[$j] = $arr[$j - 1];
        }
        //在计划插入的位置中放入元素
        $arr[$left] = $temp;
    }
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(insertionSort2($waitSort));

4. 希尔排序（Shell Sort）

4.1 希尔排序

//希尔排序
function shellSort($arr)
{
    $len = count($arr);
    //$gap一开始很大，之后每次都被减半，当$gap被减为1时，floor(1/2)得到的是0，那么下次将不再满足$gap>0条件，结束排序
    for ($gap = floor($len / 2); $gap > 0; $gap = floor($gap / 2)) {
        //注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
        //当$gap为1时，相当于执行了一次正常的插入排序
        for ($i = $gap; $i < $len; $i++) {
            //第n组的最后一个数字就应是$gap+n的位置，这里就是$i的位置
            $j = $i;
            //指向的是该组最后一个元素，记录抽出用于插入的数据
            $current = $arr[$i];

            //$j-$gap 是对比位置，指向该组倒数第2个、倒数第3个、倒数第4个元素……
            //$j-$gap值越来越小，当移动小于该组第0位置时，已超出插入位置可在范围，那么便已确定最终插入位置，结束循环
            //$j-$gap是该组中，对比位置的上一个元素，如果该值比当前抽出元素大，那么将该元素右挪$gap位，即该组右一位
            while ($j >= $gap && $current < $arr[$j - $gap]) {
                $arr[$j] = $arr[$j - $gap];
                //左挪到下一个用于对比的位置
                $j = $j - $gap;
            }
            //最终确定插入位置，将抽出元素填入其中
            $arr[$j] = $current;
        }
    }
    //返回排序后数组
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(shellSort($waitSort));

4.2 希尔排序优化

关于希尔排序的相关优化可以参照文章排序算法（四） —— 希尔排序

5. 归并排序（Merge Sort）

5.1 递归-自顶向下归并

//归并排序-自顶向下排序
function mergeSort1($arr)
{
    //先将数据切割成左右两部分，在递归最底层中，保证数组只有0或1个元素时，才返回
    $len = count($arr);
    if ($len < 2) {
        return $arr;
    }
    //将数组切割成左右两个部分
    $middle = floor($len / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);

    //使用递归，将两组数据进行排序后最终返回
    return merge1(mergeSort1($left), mergeSort1($right));
}

function merge1($left, $right)
{
    //要输出的排序数组
    $result = [];
    //$left和$right已经分别是两组有序的数据了，如果是最开始的时候，$left/$right会是只有0或1个数据，也可理解为该组数据有序的，所以不用担心

    //当两组数据有一组的数据已经全部用于排序后，那么结束该循环，再下面再填充进未用于排序的数据
    while (!empty($left) && !empty($right)) {
        //两组有序数据分别取出第一个元素（各组中最小的元素）进行对比
        if ($left[0] <= $right[0]) {
            //如果左组的元素最小，那么将其弹出并存放到要输出的排序数组中，下一步继续使用左组最小元素(原第二小)跟右边当前最小进行对比
            $result[] = array_shift($left);
        } else {
            //如果右组的元素最小，那么将其弹出并存放到要输出的排序数组中，下一步继续使用左组当前最小跟右边最小元素(原第二小)进行对比
            $result[] = array_shift($right);
        }
    }

    
    //实际上下面两个while，在实际执行时，只有一个会进入循环（因为上面的while已经保证左右至少有一组数据全部弹完了）
    //这里写两个是因为没有办法保证实际到底是左边先弹完还是右边先弹完，每两组数据对比后的结果都是不一样的，所以必须两个都写

    //如果左组还有数据没有弹完，那么代表左组剩余的数据都是很大的，只要按已有顺序弹出保存到输出 要输出的排序数组 即可
    while (!empty($left)) {
        $result[] = array_shift($left);
    }

    //如果右组还有数据没有弹完，那么代表右组剩余的数据都是很大的，只要按已有顺序弹出保存到输出 要输出的排序数组 即可
    while (!empty($right)) {
        $result[] = array_shift($right);
    }

    //最终输出排序数组，在递归中，它只代表这两组数据已经完成归并排序，不一定是最终的排序结果
    return $result;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(mergeSort1($waitSort));

5.2 循环-自底向上归并

/**
 * 自底向上归并
 * sz 是每次左右部分中元素的个数
 * 外层循环控制分组
 * 内层循环控制归并
 */
function mergeSort2($arr)
{
    $len = count($arr);
    //将数据分成两组进行循环
    // sz 的初始值为 1，每次翻倍，扩大为原排序范围的两倍
    for ($sz = 1; $sz < $len; $sz *= 2) {
        // sz子数组大小
        //$i是范围的起始位置，当排序完一遍后，则进入下一个范围（排序一次的范围是$sz+$sz），故而使用$i+=$sz+$sz
        //$i+$sz < $len：$i+$sz代表范围的中间位置，如果中间位置已经 超过 或 等于 数组长度，那么代表范围的右边已经没有数据了，应当结束循环
        for ($i = 0; $i + $sz < $len; $i += $sz + $sz) {
            //排序数组$i到min($i+$sz+$sz-1,$len-1)范围的数据，在原数组中进行排序操作
            //因为排序完当前范围后，即要接着判断下一组范围的数据。一开始
            //min($i + $sz + $sz - 1, $len - 1)：如果$len为奇数，那么，sz的偶数倍可能会大于它，所以这里使用min才保证不超过数据最大范围。-1是因为从下标0开始
            merge2($arr, $i, $i + $sz - 1, min($i + $sz + $sz, $len) - 1);
        }
    }
    //返回最终排序完成的数组
    return $arr;
}


/**
 * @title merge2
 * @param array $arr 原数组，直接保存排序数据在其上
 * @param int $l 排序范围的最左位置
 * @param int $mid 排序范围的中间位置
 * @param int $r 排序范围的最右位置
 * @author millionmile
 * @time 2020/08/04 17:50
 */
function merge2(array &$arr, int $l, int $mid, int $r)
{
    //复制一份 排序范围内的数据，用于保存原数组被下面替换数据前的原状态
    $aux = array_slice($arr, $l, $r + 1 - $l);

    //$i是左半部分的指针，开始位置为$l
    $i = $l;
    //$i是右半部分的指针，开始位置为$mid+1
    $j = $mid + 1;

    //$k是原数组的指针，这里从要排序范围开始，所以初始值是$l，当变成$r时，即完成排序范围内的排序
    for ($k = $l; $k <= $r; $k++) {
        //排序过程中存在四种情况，下面分别对齐进行处理
        switch (true) {
            //当左半部分的指针的指针已经大于中间位置（左半部分的数据已经全部放到原数组）时
            case $i > $mid:
                //直接将右半部分剩余的数据全部按顺序放入到数组中
                $arr[$k] = $aux[$j - $l];
                $j++;
                break;
            //当右半部分的指针已经大于右边范围（右半部分的数据已经全部放到原数组）时
            case $j > $r:
                //直接将左半部分剩余的数据全部按顺序放入到数组中
                $arr[$k] = $aux[$i - $l];
                $i++;
                break;
            //如果左半部分取出的元素比较小
            case $aux[$i - $l] < $aux[$j - $l]:
                //将左半部分取出的元素放入原数组
                $arr[$k] = $aux[$i - $l];
                //然后左半部分指针加一，不再对其进行比较使用
                $i++;
                break;
            //剩余的情况只有一种：右半部分取出的元素比较小
            default:
                //将右半部分取出的元素放入原数组
                $arr[$k] = $aux[$j - $l];
                //然后右半部分指针加一，不再对其进行比较使用
                $j++;
        }
    }
}


$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];

print_r(mergeSort2($waitSort));

5.3 小结

如果要排序一亿个数，使用归并排序和分布式来进行处理是一种较好的选择：

先将一亿个数切割成n个数组，分别丢给n台服务器进行处理
各台服务器内部使用任意一种排序方式都可，只需完成正确的排序就行
等待获取到各台服务器的最终排序结果后，再进行两两进行归并排序，得到最终的排序结果

6. 快速排序（Quick Sort）

6.1 快速排序

//快速排序
function quickSort(&$arr, int $left = 0, int $right = null)
{
    $len = count($arr);
    //如果是顶层递归，即外部调用，是没有传left和right的，这是right要默认为数组最右范围
    if ($right === null) {
        $right = $len - 1;
    }

    if ($left < $right) {
        //获取到基准当前所在位置
        $partitionIndex = partition($arr, $left, $right);
        //对基准左半部分使用递归-快速排序
        quickSort($arr, $left, $partitionIndex - 1);

        //对基准右半部分使用递归-快速排序
        quickSort($arr, $partitionIndex + 1, $right);
    }
    return $arr;
}

function partition(&$arr, $left, $right)
{
    // 分区操作
    //设定基准值[排序前所在下标]
    $pivot = $left;
    //实际基准边界，随着排序向右挪
    $index = $pivot + 1;

    //当基准边界已经到达排序范围，终止排序
    for ($i = $index; $i <= $right; $i++) {
        //如果当前指针所在值小于基准值
        if ($arr[$i] < $arr[$pivot]) {
            //将该值跟基准当前所在值进行交换
            swap($arr, $i, $index);
            //调整基准边界，最后一次调整后，没有再进行替换，会导致基准边界大了1个位置
            $index++;
        }
    }
    //最后将基准和当前实际基准边界上的值进行互换
    swap($arr, $pivot, $index - 1);

    //返回基准实际所在位置(-1是因为上面$index++的最后一次，是没有替换的)
    return $index - 1;
}

//交换数组中两个元素的值
function swap(&$arr, $i, $j)
{
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
    return $arr;
}


$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(quickSort($waitSort));

6.2 快速排序优化

关于快速排序的相关优化可以参照文章《快速排序的4种优化》

7. 堆排序（Heap Sort）

7.1 堆排序

这里先给大家一个堆结构形成的相对应数组示意图，方便清晰理解在这里插入图片描述

/**
 * 堆排序
 * 1.构建堆 buildHeap()
 * 2.对堆进行排序 heapSort()
 * @param $arr
 */
function heapSort(array $arr)
{
    //构建堆（大顶堆），已经进行了大小调整，堆顶便是最大数
    buildHeap($arr);
    $len = count($arr);

    //$i既是最后一个子节点的下标，同样也是砍断后的树的节点个数
    //当$i=0时，代表树已被砍完，没有必要再进行排序，则满足条件$i>0即可
    for ($i = $len - 1; $i > 0; $i--) {
        //交换堆顶和末尾节点，末尾节点便转为了当前树的最大数，下一次循环$i变小，便跳过了末尾节点的位置无需再排，即 砍断
        swap($arr, 0, $i);
        //砍断仅是逻辑上的说法，实际是跳过最后一个节点的排序
        //砍断 即 当前树的节点个数-1，即$i等于节点个数，所以第二参数传入$i，调整砍断后的树节点大小位置
        heapify($arr, $i, 0);
    }
    return $arr;
}

/**
 * 将待排序数组构建为大顶堆
 * @param $arr
 */
function buildHeap(array &$arr)
{
    $len = count($arr);
    //该树的最后一个节点
    $last_node = $len - 1;
    //最后一个节点的父亲节点
    $parent = ($last_node - 1) / 2;
    //自底向上对父亲节点做 hepify
    for ($i = $parent; $i >= 0; $i--) {
        heapify($arr, $len, $i);
    }
}

/**
 * 对某节点下的子树进行排序，确保当前父节点大于左右子节点
 * @param array $data 待排序数组
 * @param int $len 当前树的节点个数
 * @param int $root 当前子树的根节点所在下标
 */
function heapify(array &$data, int $len, int $root)
{
    //递归的出口，当前根节点位置已超出树的范围，那么不再进行排序
    if ($root >= $len) {
        return;
    }
    //获取当前树的左节点位置
    $left = $root * 2 + 1;

    //获取当前树的右节点位置
    $right = $root * 2 + 2;

    $max = $root; //子树节点最大值

    //$right<$len代表右节点存在。$data[$max] < $data[$right]代表父节点小于右节点
    if ($right < $len && $data[$max] < $data[$right]) {
        //这时候，最大值应为右节点，这里记录的是最大值所在的下标位置
        $max = $right;
    }
    //$left < $len代表左节点存在。$data[$max] < $data[$right]代表父节点小于左节点
    if ($left < $len && $data[$max] < $data[$left]) {
        //这时候，最大值应为左节点，这里记录的是最大值所在的下标位置
        $max = $left;
    }
    //找到了当前子树的最大值，用最大值与其原父亲节点进行交换
    //如果父节点均大于左右孩子，则不用交换
    if ($max != $root) {
        //用最大值与其原父亲节点进行交换
        swap($data, $max, $root);

        //最大值更改后，其下子树位置不一定满足左右子节点均小于父节点($max)的情况，这里需要再对其子树进行排序
        heapify($data, $len, $max);
    }
}

/**
 * @title 交换数组中两个下标元素的位置
 * @param array $data
 * @param int $i
 * @param int $j
 */
function swap(array &$data, int $i, int $j)
{
    $temp = $data[$i];
    $data[$i] = $data[$j];
    $data[$j] = $temp;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(heapSort($waitSort));

8. 计数排序（Counting Sort）

8.1 计数排序

//计数排序
function countingSort($arr, $maxValue)
{
    $bucket = [];
    $sortedIndex = 0;
    $arrLen = count($arr);
    $bucketLen = $maxValue + 1;

    for ($i = 0; $i < $arrLen; $i++) {
        if (!isset($bucket[$arr[$i]])) {
            $bucket[$arr[$i]] = 0;
        }
    }
    for ($j = 0; $j < $bucketLen; $j++) {
        while (isset($bucket[$j]) && $bucket[$j] > 0) {
            $arr[$sortedIndex++] = $j;
            $bucket[$j]--;
        }
    }
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(countingSort($waitSort, 10));

8.2 计数排序与计数排序的优化

关于计数排序的相关优化可以参照文章《计数排序与计数排序的优化》

9. 桶排序（Bucket Sort）

9.1 桶排序

//桶排序

//每个桶重的数据需要各自去进行排序，这里使用插入排序来进行处理
function insertionSort($arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $preIndex = $i - 1;
        $current = $arr[$i];
        while ($preIndex >= 0 && $arr[$preIndex] > $current) {
            $arr[$preIndex + 1] = $arr[$preIndex];
            $preIndex--;
        }
        $arr[$preIndex + 1] = $current;
    }
    return $arr;
}


function bucketSort($arr, $bucketSize)
{
    $len = count($arr);
    if ($len === 0) {
        return $arr;
    }

    //桶排序需要确定数据中的最小值和最大值
    $minValue = $arr[0];
    $maxValue = $arr[0];
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] < $minValue) {
            //获得数据中的最小值
            $minValue = $arr[$i];
        } elseif ($arr[$i] > $maxValue) {
            //获得数据中的最大值
            $maxValue = $arr[$i];
        }
    }

    //设置桶的数量为5
    $bucketSize = 5;

    $buckets = [];
    for ($i = 0; $i < count($buckets); $i++) {
        $buckets[$i] = [];
    }

    //利用映射函数将数据分配到各个桶中
    for ($i = 0; $i < count($arr); $i++) {
        //floor(($arr[$i] - $minValue) / $bucketSize)是将相邻差别不大的几个数放在一起
        $buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
    }

    $arr = [];
    for ($i = 0; $i < count($buckets); $i++) {
        //将5个桶依次循环，从最小的桶开始拿排序后的数据
        $buckets[$i] = insertionSort($buckets[$i]);                      // 对每个桶进行排序，这里使用了插入排序
        for ($j = 0; $j < count($buckets[$i]); $j++) {
            //将桶排序后数据一一放入
            $arr[] = $buckets[$i][$j];
        }
    }
    return $arr;
}

$waitSort = [3, 6, 8, 1, 2, 9, 10, 7, 5, 4];
print_r(bucketSort($waitSort, 10));

10. 基数排序（Radix Sort）

10.1 基数排序

/**
 * @title 基数排序
 * @param array $arr 待排序数组
 * @param int $maxDigit 数组中最大数的位数
 * @return array
 */
function radixSort(array $arr, int $maxDigit)
{
    //临时存放数据的额外空间
    $counter = [];

    //默认值，用来求相应位数下的值
    $mod = 10;
    $dev = 1;

    //获取待排序数组的长度，用于下面两次内部循环
    $len = count($arr);

    //先根据个位数进行第一轮排序，再根据十位数进行第二轮排序，根据百位数进行第三轮排序……
    for ($i = 0; $i < $maxDigit; $i++, $dev *= 10, $mod *= 10) {
        for ($j = 0; $j < $len; $j++) {
            //如果当前没有该值存在，则直接跳过
            if (!isset($arr[$j])) {
                continue;
            }

            //获取到当前数字的该位数上的数字
            $bucket = intval(($arr[$j] % $mod) / $dev);
            //$counter[$bucket]一开始是不存在的，这里进行初始化。之后几轮汇总，$counter[$bucket]在这里是存在的，虽然其内无值
            if (!isset($counter[$bucket])) {
                $counter[$bucket] = [];
            }
            //将数字存放到相应额外空间中
            $counter[$bucket][] = $arr[$j];
        }

        //清空最终数组，用来存放排序后的数据
        $arr = [];

        //循环原未排序数组的次数
        for ($j = 0; $j < $len; $j++) {
            //如果额外空间中存在，那么进行输出操作
            if (isset($counter[$j])) {
                //弹出额外空间中的值，如果全部弹完，那么就跳出弹出循环
                while ($value = array_shift($counter[$j])) {
                    //保存到新的排序后数组中
                    $arr[] = $value;
                }
            }
        }
    }
    //输出最终排序的数组
    return $arr;
}

$waitSort = [3, 6, 8, 1, 13, 10, 7, 5, 4, 11];
print_r(radixSort($waitSort, 10));

10.2 基数排序优化

关于基数排序的相关优化可以参照文章《基数排序的性能优化》

总结

写了这么多，那到底什么排序是最好最快的排序呢？答案是不存在。每种排序都有自己的优点和缺点，有的排序快但占用空间多，有的排序看似稳定快速，但如果面对某种极端情况（待排序列已经有大部分顺序是排序好的）反而速度会变慢。存在即有理。排序算法有好有坏，那如果综合使用呢？根据情况去使用不同的排序算法。

例如：当快速排序达到一定深度后，划分的区间很小时，再使用快速排序的效率不高。当待排序列的长度达到一定数值后，可以使用插入排序。由《数据结构与算法分析》(Mark Allen Weiness所著)可知，当待排序列长度为5~20之间，此时使用插入排序能避免一些有害的退化情形。

排序算法其实在现实业务中，并没有多大的意义：如PHP，一个sort()方法足以解决一切，其他语言亦有类似方法。那么为什么还要学习掌握排序算法呢？与其说我们学习排序算法，倒不如说我们是学习算法的基本思想和方法，理解各算法思想，掌握编写方法，才能更好地运用到其他需要使用到算法的业务情景中。排序是算法的经典例子，哪怕是通过其他题目学习算法亦无不可，排序只是经典且基础罢了。

参考文献

被排序算法吊打之—冒泡排序你需要了解的三种优化