快速排序法通过设置一个中间值,把要排序的数组进行递归,如果按从小到大排序,小于中间值的放左边,中间值在中间,大于中间值的放右边,最后合并数组得出的结果。

一、快速排序法

<?php
$arr = [11, 3, 10, 8, 7, 4, 2, 1, 9, 3, 5, 15];
 
class quickSort
{
    public static function qSort($arr)
    {
        if (count($arr) <= 1) {
            return $arr;
        }
 
        // 中间值
        $middle = $arr[0];
 
        $left = $right = [];
 
        foreach ($arr as $key => $val) {
            if ($key == 0) {
                continue;
            }
            if ($val > $middle) {
                $right[] = $val;
            } else {
                $left[] = $val;
            }
        }
 
       
        $left = self::qSort($left, $n);
        $right = self::qSort($right, $n);
       
        return array_merge($left, [$middle], $right);
    }
}
 
var_export(quickSort::qSort($arr));

执行结果:

array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, 10 => 11, 11 => 15, )

二、运行过程

加入对每次数据的记录,查看每次的排序流程。

<?php
$arr = [11, 3, 10, 8, 7, 4, 2, 1, 9, 3, 5, 15];
echo var_export($arr) . "<br/>";
 
class quickSort
{
    public static function qSort($arr, $n)
    {
        if (count($arr) <= 1) {
            return $arr;
        }
 
        // 中间值
        $middle = $arr[0];
 
        $left = $right = [];
 
        foreach ($arr as $key => $val) {
            if ($key == 0) {
                continue;
            }
            if ($val > $middle) {
                $right[] = $val;
            } else {
                $left[] = $val;
            }
        }
 
        $n++;
        $left = self::qSort($left, $n);
        echo '第' . $n . '次(left)' . "<br/>" . var_export($left);
        $right = self::qSort($right, $n);
        echo '第' . $n . '次(right)' . "<br/>" . var_export($right);
 
        echo '第' . $n . '次(all)' . "<br/>" . var_export(array_merge($left, [$middle], $right));
        return array_merge($left, [$middle], $right);
    }
}
 
var_export(quickSort::qSort($arr, $n = 0));

执行结果:

array ( 0 => 11, 1 => 3, 2 => 10, 3 => 8, 4 => 7, 5 => 4, 6 => 2, 7 => 1, 8 => 9, 9 => 3, 10 => 5, 11 => 15, )
array ( 0 => 1, )第3次(left)
array ( 0 => 3, )第3次(right)
array ( 0 => 1, 1 => 2, 2 => 3, )第3次(all)
array ( 0 => 1, 1 => 2, 2 => 3, )第2次(left)
array ( )第6次(left)
array ( 0 => 5, )第6次(right)
array ( 0 => 4, 1 => 5, )第6次(all)
array ( 0 => 4, 1 => 5, )第5次(left)
array ( )第5次(right)
array ( 0 => 4, 1 => 5, 2 => 7, )第5次(all)
array ( 0 => 4, 1 => 5, 2 => 7, )第4次(left)
array ( 0 => 9, )第4次(right)
array ( 0 => 4, 1 => 5, 2 => 7, 3 => 8, 4 => 9, )第4次(all)
array ( 0 => 4, 1 => 5, 2 => 7, 3 => 8, 4 => 9, )第3次(left)
array ( )第3次(right)
array ( 0 => 4, 1 => 5, 2 => 7, 3 => 8, 4 => 9, 5 => 10, )第3次(all)
array ( 0 => 4, 1 => 5, 2 => 7, 3 => 8, 4 => 9, 5 => 10, )第2次(right)
array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, )第2次(all)
array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, )第1次(left)
array ( 0 => 15, )第1次(right)
array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, 10 => 11, 11 => 15, )第1次(all)
array ( 0 => 1, 1 => 2, 2 => 3, 3 => 3, 4 => 4, 5 => 5, 6 => 7, 7 => 8, 8 => 9, 9 => 10, 10 => 11, 11 => 15, )