排序算法-快速排序

快速排序

思路:就是找一个元素,然后依次将数组中的元素和这个数比较,大于的放到一个数组$max_array,小于的放到一个数组$min_array,然后再次递归调用,最后的元素只有一个的时候,合并$min_array,$x,$max_array,就是排序好的数组。

时间复杂度: 第一步:计算划分的时间,理论上是二分划分,所以时间复杂度是O(log2N) 第二步:计算划分之后比较的次数,时间复杂度是O(N) 所以理想复杂度就是:O(Nlog2N)

快速排序算法

<?php

$arr = array(9, 5, 3,4, 2, 1, 7, 6, 8);

function quick_sort($arr)
{
    if (!is_array($arr)) {
        return false;
    }

    $length = count($arr);
    //为空和只有一个元素,都直接返回
    if ($length <= 1) {
        return $arr;
    }

    $left = $right = array();
    $key = $arr[0];
    for ($i = 1; $i < $length; $i++) {
        if ($arr[$i] < $key) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    $left = quick_sort($left);
    $right = quick_sort($right);
    return array_merge($left, array($key), $right);
}

print_r(quick_sort($arr));