快速排序

常规方法，快速排序

<?php

/**
 * 思路：
 * 1、找到当前数组中的任意一个元素（一般选择第一个元素，因为选择第一个元素较为简单，选择其他元素还需要多写一些不必要的代码，干嘛非要给自己找麻烦哩）作为比较的标准
 * 2、新建两个空数组，用于存放比比较的元素大或者小的元素，当遍历整个数组元素时，如果遍历到的元素比当前元素要小，则将此元素放到左边的数组，比当前元素大，则放到右边的数组中
 * 3、再以同样的方式去遍历左边的数组和右边的数组
 *
 * 递归点：只要是需要比较的数组中的元素个数大于 1，那么就需要递归，只有当数组中的元素的个数等于 1 的时候，则停止递归，不需要比较
 *
 * @param array $arr
 * @return array
 */
function quick_sort(array $arr) : array
{
    // 判断参数是否是一个数组
    if (!is_array($arr)) return [];

    // 递归出口：数组长度为 1 ，则直接返回数组
    $length = count($arr);
    if ($length <= 1) return $arr;

    // 数组元素有多个，则定义两个空数组
    $left = $right = [];

    // 把第一个元素当作比较的对象
    for ($i = 1; $i < $length; $i++) {
        // 判断当前元素的大小
        if ($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    // 递归调用
    $left = quick_sort($left);
    $right = quick_sort($right);

    // 合并所有的结果
    return array_merge($left, [$arr[0]], $right);
}

//$arr = [4, 7, 6, 5, 3, 2, 8, 1];
$arr = [22, 7, 1, 34, 435, 8, 523, 3, 21, 2, 24, 654, 55, 32, 12];
$res = quick_sort($arr);
echo join('-', $res);

“挖坑法” 快速排序

<?php

/**
 * "挖坑法" 快速排序
 *
 * @param array $arr
 * @return array
 */
function quick_sort(array $arr) : array
{

    switch (count($arr)) {
        case 0 :
            return [];
        case 1 :
            return $arr;
        case 2 :
            return ($arr[0] < $arr[1]) ? [$arr[0], $arr[1]] : [$arr[1], $arr[0]];
    }

    $pivot = $arr[0];
    $leftHead = 0;
    $rightHead = count($arr) - 1;
    $index = 0;  // 需要填充处
    $compare = 'right';  // 拿数组左侧的数据与数组右侧的数据进行比较

    while (true) {
        if ($leftHead == $rightHead) {
            $left = array_slice($arr, 0, $leftHead);
            $right = array_slice($arr, ($leftHead + 1));
            $mid = [$pivot];
            return array_merge(quick_sort($left), $mid, quick_sort($right));
        }
        if ('right' == $compare) {
            // 如果右指针的数小于基准数，那么将这个数填入基准数里面
            if ($arr[$rightHead] < $pivot) {
                $arr[$index] = $arr[$rightHead];
                $leftHead++;
                $index = $rightHead;
                $compare = 'left';  // 拿左侧的数据开始进行排序
            } else {
                $rightHead--;  // 如果比他大
            }
        } else {  // $compare == 'left'
            if ($arr[$leftHead] > $pivot) {  // 如果大于基准数，填充右边的 index
                $arr[$index] = $arr[$leftHead];
                $index = $leftHead;
                $rightHead--;
                $compare = 'right';
            } else {
                $leftHead++;
            }
        }
    }

}

//$arr = [4, 7, 6, 5, 3, 2, 8, 1];
$arr = [22, 7, 1, 34, 435, 8, 523, 3, 21, 2, 24, 654, 55, 32, 12];
$res = quick_sort($arr);
echo join('-', $res);