快速排序

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

 1) {
        $temp = $arr[0];
        $x = $y = array();
        for($i = 1; $i < count($arr); $i++) {
            if($arr[$i] < $temp) {
                $x[] = $arr[$i];
            } else {
                $y[] = $arr[$i];
            }
        }
        $x = quick_sort($x);
        $y = quick_sort($y);
        return array_merge($x, array($temp),  $y);
    } else {
        return $arr;
    }
}
$arr = array(1,4,5,89,22,44,5,33,6,7,82,332);
$result = quick_sort($arr);
print_r($result);

最坏的情况下就是O(n2)



Tagged , . Bookmark the permalink.

Comments are closed.