快速排序是对冒泡排序算法的一种改进。
基本思想:通过一趟排序将要排序的数组分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据小,然后再按此方法对两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序。
快速排序平均算法时间复杂度为O(nlogn),它最坏的情况为O(n^2).
代码实现
方法一:
function quickSort($arr) {
$count = count($arr);
if ($count<2) {
return $arr;
}
//创建临时数组,以基准值为分界线,大于基准值的放在右侧,
//小于基准值的放在左侧
$leftArr = $rightArr = [];
//基准值, 一般取数组第一个元素
$middle = $arr[0];
for($i=1;$i<$count; $i++) {
if ($arr[$i]<$middle) {
$leftArr[] = $arr[$i];
} else {
$rightArr[] = $arr[$i];
}
}
//递归,将左右数组排序
$leftArr = quickSort($leftArr);
$rightArr = quickSort($rightArr);
//将排好序的临时数组合并
return array_merge($leftArr,[$middle],$rightArr);
}
方法二:
function quick_sort($arr) {
$count = count($arr);
if($count<2) {
return $arr;
}
$i = 0;
$j = $count - 1;
//基准值
$key = $arr[0];
while($i<$j) {
//首先从后往前比较,比基准值大的放过,比基准值小的做交换
while($i<$j && $arr[$j]>=$key) {
$j--;
}
//交换
$arr[$i] = $arr[$j];
$arr[$j] = $key;
//再从前往后比较,比基准值小的放过,比基准值大的做交换
while($i<$j && $arr[$i] <= $key) {
$i++;
}
$arr[$j] = $arr[$i];
$arr[$i] = $key;
}
//经过一轮交换,基准值左侧全部比基准值小,基准值右侧比基准值大,但左右两侧并不一定是排好序的,
//然后进行递归,将基准值左右两侧进行排序
if ($i==0) {
$left = [];
} else {
$left = quick_sort(array_slice($arr,0,$i));
}
if($i == $count-1) {
$right = [];
} else {
$right = quick_sort(array_slice($arr, $i+1, $count+1-$i));
}
//将排好序的数组进行合并返回
return array_merge($left, [$key], $right);
}