排序算法-快速排序

快速排序

思路：就是找一个元素，然后依次将数组中的元素和这个数比较，大于的放到一个数组$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));