PHP版算法--快速排序的实现（第二种方法）

使用第一种方法实现的快速排序相对来说要容易理解一点，第二种方法相对来说不好理解。为此，通过我自己的学习，我画了一张图，以此增加理解记忆。

如果还没有弄明白，那么使用一个最古老的方法，将数组元素值代入到代码中，一遍一遍跑下来，这样巩固了知识又加强了自己的理解。

举个例子：如下文将使用到的数组。

1）$start = 0开始位置

2）$end = 4。4的由来是数组长度减一，因为把基准元素值，单独拿了出来

下面开始代码实现

<?php

/**
 * 快速排序
 * 
 * @param array $arr    待排序的数组
 * @param int   $start  开始位置
 * @param int   $end    结束位置
 * 
 * @return array $arr   排序好的数组
 **/
function quick_sort_two(array &$arr, int $start, int $end) {
    if ($start >= $end) {
        return;
    }

    $left = $start;
    $right = $end; 
    // 将数组第一值作为基准数
    $pivot = $arr[$start];

    while($left < $right) {
        // 从右向左查找小于基准数的值
        while($left < $right && $arr[$right] >= $pivot) {
            // 遍历数组元素，从右向左比较，直到找到小于基准值的数
            $right--;
        }
        // 找到小于基准值的后，与之互换位置
        $arr[$left] = $arr[$right];
        

        // // 从左向右查找小于基准数的值
        while ($left < $right && $arr[$left] <= $pivot) {
            // 遍历数组元素，从左向左向较，直到找到大于基准值的数
            $left++;
        }
        // 找到大于基准值的后，与之互换位置
        $arr[$right] = $arr[$left];
    }
    // 交换基准值
    $arr[$right] = $pivot;
 
    // 再次递归调用
    quick_sort_two($arr, $start, $right-1);
    quick_sort_two($arr, $right+1, $end);
    return $arr;
}


$arr = [5,11,1,6,10];

// 计算程序运行的时间（微秒）
$startTime = microtime(true);
$a = quick_sort_two($arr,0,intval((count($arr)-1)));
print_r($a);
$endTime = microtime(true);
echo $endTime - $startTime;

看运行结果

Array ( [0] => 1 [1] => 5 [2] => 6 [3] => 10 [4] => 11 ) 1.2874603271484E-5
    
Array ( [0] => 1 [1] => 5 [2] => 6 [3] => 10 [4] => 11 ) 9.0599060058594E-6

可以看到，多次刷新，排序所花费的时间不一样。

快速排序是一种不稳定的排序算法。

我是温新，每天进步一点点，就一点点。

2021-06-03