快速排序是对冒泡排序算法的一种改进。

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

快速排序平均算法时间复杂度为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);

}