Blog

It's a Wonderful Life

快速排序算法

2017-02-28 22:01 Posted in Learn with PHP , algorithm

由于使用到了递归，快速排序算法时间复杂度为O(nlogn)，这意味着只有加倍数组的长度才会增加运算时间，相较于冒泡排序要快很多。冒泡排序算法由于要对整个数组进行两次遍历，所以它的时间复杂度为O(n^2)。

以下是快速排序算法的代码实现。

<?php
function quick_sort($array)
{
    if (count($array) <= 1) return $array;
    
    $key = $array[0];
    
    $left_arr = array();
    $right_arr = array();
    
    for ($i=1; $i<count($array); $i++)
    {
        if ($array[$i] <= $key)
            $left_arr[] = $array[$i];
        else
            $right_arr[] = $array[$i];
    }
    
    $left_arr = quick_sort($left_arr);
    
    $right_arr = quick_sort($right_arr);
    
    return array_merge($left_arr, array($key), $right_arr);
}