快速排序(二分法排序)#

算法实现原理#

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

实现代码#

$array = [2, 4, 9, 3, 5, 7, 8, 1, 6, 10];

function quick_sort($array) {
    // 判断是否需要运行,因下面已拿出一个中间值,这里<=1
    if (count($array) <= 1) {
        return $array;
    }

    $middle = $array[0]; // 中间值

    $left = []; // 接收小于中间值
    $right = []; // 接收大于中间值
    for($i = 1; $i < count($array); $i++) {
        if ($array[$i] < $middle) {
            // 小于中间值
            $left[] = $array[$i];
        } else {
            // 大于中间值
            $right[] = $array[$i];
        }
    }

    // 递归排序划分好的2边
    $left = quick_sort($left);
    $right = quick_sort($right);

    // 合并排序后的数据,别忘了合并中间值
    return array_merge($left, [$middle], $right);
}

$result = quick_sort($array);

print_r($result);

结果:
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 7
    [7] => 8
    [8] => 9
    [9] => 10
)