概念

快速排序基于分治思想来实现。

  1. 分解:数组A[start,end]被划分为两个(可能为空)子数组A[start,postion-1]和A[postion+1,end]中的,使A[start,postion-1]的每一个元素都小于等于A[postion],A[postion+1,end]的每一个元素都大于等于A[postion]。
  2. 解决:通过递归调用快速排序,对子数组A[start,postion-1]和A[postion+1,end]进行排序。
  3. 合并:因为数组是原址排序,因此A[start,end]是有序的。

数组的划分(解决)实现思想图

PHP实现快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function quickSort(&$array,$start,$end)
{
if ($start < $end) {
$postion = partition($array, $start, $end);
quickSort($array,$start,$postion-1);
quickSort($array,$postion+1,$end);
}
}

function partition(&$arr,$start,$end) {
$flag = $arr[$end];
$i = $start-1;
for ( $j=$start; $j<= $end-1; $j++) {
if($arr[$j] <= $flag) {
$i = $i+1;
swap($arr,$i,$j);
}
}
swap($arr,$i+1,$end);

return $i+1;
}

function swap (&$arr,$exist,$replace) {
$temp = $arr[$exist];
$arr[$exist] = $arr[$replace];
$arr[$replace] = $temp;
}

$array = array(1,6,5,4);
quickSort($array,0,3);
var_dump($array);