快速排序 PHP四种实现

快速排序和冒泡排序一样也属于交换排序，通过比较、交换元素的位置来达到排序的目的。

区别在于冒泡排序每轮只把1个元素冒泡到数列的一端，而快速排序则在每一轮挑选一个基准元素 (pivot)，并让其他比它大的元素移动到数列的一端，比它小的元素移动到数列的另一端，从而把数列拆分成两个部分。

这种思想叫 分治法，原数列在每轮被拆分为两部分，每一部分在下一轮又拆分为两部分，直到不可再分为止。

假如元素个数是 n，那么平均情况下需要 logn 轮，因此快速排序算法的时间复杂度是 O(nlogn)。

基准元素的选择

在 分治过程中以基本元素为中心，将其他元素移动至基础元素的左右两边。

基准元素的选择，一般是选数列的第一个元素，这样在大多数的情况下是没问题的。但如果有一个原本逆序的数列需要变成顺序数列。这种情况下，数列的第一个元素要么是最大数，要么是最小数，无法发挥分治法的优势。快速排序需要进行 n 轮排序，时间复杂度退化成了 O(n^2^)。

为了避免这种情况的发生，我们可以随机选择一个元素作为基准元素，并且让基准元素和数列首位元素交换位置。这样一来，即使是完全逆序的情况下，也能有效的将数组分割为两个部分。

当然随机选择基准元素，也会有极小的几率选中最大值或最小值，同样会影响到分治的效果。所以，快速排序的平均时间复杂度是O(nlogn)，但最坏的情况下时间复杂度是 O(n^2^)

简单写法

这个写法比较直观，但缺点是损失了大量的空间，并且使用了效率较低的 array_marge 函数。

 function quick_sort($arr)
{
    $arr_count = count($arr);

    // 如果是空数组 则直接返回
    if($arr_count < 1)
     return $arr;

    // 获取基准坐标
    $pivot = $arr[0];
    // 设置两个空数组用来存储 大小值
    $left = $right = [];
    
    for ($i=1; $i < $arr_count; $i++) { 
        
        if($arr[$i] < $pivot){
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    
    // 比基准数小的再次排序
    $left_res = quick_sort($left);

    // 比基准数大的再次排序
    $right_res = quick_sort($right);

    // 对结果进行组装
    return array_merge($left_res,[$pivot],$right_res);

}
var_dump(quick_sort($arr));

双边循环法

让数列中的元素根据自身大小，交换到基准元素的两边。

<?php
function quick_sort_refer(&$arr, $start, $end)
{
    // 递归结束条件
    if($start >= $end) return;
    $left = $start;
    $right = $end;

    // 设置基准元素，就是获取每次排序的第一个元素
    $pivot = $arr[$left];

    while ($left != $right) {
    
        /**
         * 从 right指针开始，让指针指向元素和基准元素做比较。如果大于或等于 基准元素，则 right 指针向左移动
         * 如果小于基准元素，则 right停止移动，开始 left指针移动
         */
        while ($left < $right && $arr[$right] >= $pivot) {
            $right--;
        }

        /**
         * left 指针开始移动，让指针指向元素和基准元素做比较。如果小于或等于 基准元素，则指针向右移动；
         * 如果大于基准元素则 left 指针停止移动。
         */
        while ($left < $right && $arr[$left] <= $pivot) {
            $left++;
        }

        // 交换left right 指针 所指向的元素
        if($left < $right) {
            $temp = $arr[$left];
            $arr[$left] = $arr[$right];
            $arr[$right] = $temp;
        }

    }

    // 基准元素和指针重合点交换
    $arr[$start] = $arr[$left];
    $arr[$left] = $pivot;

    // 根据基准元素分成两部分在进行递归排序
    quick_sort_refer($arr, $start, $left - 1);
    quick_sort_refer($arr, $left + 1,$end);
}

$arr = [3,2,5,6,4,9,1,23,46,72];
$arr_count = count($arr);
quick_sort_refer($arr,0, $arr_count - 1);
var_dump($arr);
?>

单边循环法

双边循环法是 从数组的两边交替遍历元素，虽然更直观，但代码相对繁琐，而单边遍历指从数组的一边对元素进行遍历和替换。

首先选定基准元素 pivot，同时设置一个 mark 指针指向数列起始位置，这个 mark 指针代表基准元素的边界。

接下来从基准元素的下一个位置开始遍历数组。

如果遍历到的元素大于基准元素，就继续往后遍历。

如果遍历到的元素小于基准元素，则需要处理两个逻辑:

• 第一：把 mark 指针向右移动一位，因为小于基准元素的区域边界增大了1；
• 第二：让最新遍历到的元素和 mark 指针所在位置的元素交换位置，因为最新遍历的元素属于小于 基准元素区域。

<?php
function quick_sort_refer(&$arr, $start, $end)
{
    // 递归结束条件
    if($start >= $end) return;
    

    // 设置基准元素，就是获取每次排序的第一个元素
    $pivot = $arr[$start];
    $mark = $start;

    for ($i=$start + 1; $i < $end; $i++) { 
        
        if($arr[$i] < $pivot) {
            $mark ++;
            $temp = $arr[$mark];
            $arr[$mark] = $arr[$i];
            $arr[$i] = $temp;
        }

    }

    $arr[$start] = $arr[$mark];
    $arr[$mark] = $pivot;
    

    // 根据基准元素分成两部分在进行递归排序
    quick_sort_refer($arr, $start, $mark - 1);
    quick_sort_refer($arr, $mark + 1,$end);
}

$arr = [3,2,5,6,4,9,1,23,46,72];
$arr_count = count($arr);
quick_sort_refer($arr,0, $arr_count - 1);
var_dump($arr);    
?>

非递归循环

递归的本质，就是用了一个方法调用栈。每次进入一个新的方法，相当于入栈；每次有方法返回，相当于出栈；所以把原先的递归实现转换为一个栈的实现，在栈中存储每次方法调用的参数。

每次循环，都会先让栈顶的元素出栈，然后再进行分治，并按照基准元素的位置分成左右两部分，左右两部分再分别入栈。当栈为空时，说明排序已经完毕，退出循环。

<?php
 
function quick_sort_stack(&$arr, $start, $end)
{
    // 将数列的起止下标，入栈
    $stack = [];
    $root_param['start'] = $start;
    $root_param['end'] = $end;
    array_push($stack, $root_param);

    // 如果队列空了，就停止循环
    while (!empty($stack))
    {
        $param = array_pop($stack);

        // 设置基准元素，就是获取每次排序的第一个元素
        // 在之前的版本中，这个起始值和结束值需要通过递归来传递不同的值，现在用栈实现。
        $pivot = $arr[$param['start']];
        $mark = $param['start'];

        for ($i=$param['start'] + 1; $i < $param['end']; $i++) { 
            
            if($arr[$i] < $pivot) {
                $mark ++;
                $temp = $arr[$mark];
                $arr[$mark] = $arr[$i];
                $arr[$i] = $temp;
            }

        }

        $arr[$param['start']] = $arr[$mark];
        $arr[$mark] = $pivot;

        // 根据基准元素分为两部分 把每部分的下标入栈
        if($param['start'] < ($mark -1)) {
            $left_param['start'] = $param['start'];
            $left_param['end'] = ($mark - 1);
            array_push($stack, $left_param);
        }

        if(($mark +1 ) < $param['end']) {
            $right_param['start'] = ($mark + 1);
            $right_param['end'] = $param['end'];
            array_push($stack, $right_param);
        }

    }

}
$arr = [3,2,5,6,4,9,1,23,46,72];
$arr_count = count($arr);
quick_sort_stack($arr,0, $arr_count - 1);
var_dump($arr);
?>

---

本文章参考：《漫画算法：小灰的算法之旅》