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