MENU

快速排序 PHP四种实现

2021 年 09 月 14 日 • 阅读: 116 • 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);
?>

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

CC版权: 本篇博文采用《CC 协议》,转载必须注明作者和本文链接