在一堆基础算法里面,快排不算难的,虽然平时也基本没用到,但却是经常被面试官考察的玩意,没有理解就很痛苦,理解了之后就觉得很容易。

首先,来张经典的动图:

慢动作可以看:在线动画演示各种排序算法过程 - aTool在线工具

这慢动作看得是真的爽,这还有什么是不能理解呢?快速排序是一种交换类排序,大一学C语言时候学的冒泡也是交换类排序,还记得怎么写么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//先生成一个乱序的数组
$arr = range(0, 30);
shuffle($arr);
echo implode(' ', bubbleSort($arr));

function bubbleSort($integerArray) {
$num = sizeof($integerArray);
for ($i=0; $i < $num - 1 ; $i++) {
for ($j=0; $j < $num - $i -1; $j++) {
if ($integerArray[$j] > $integerArray[$j + 1]) {
$Temp = $integerArray[$j + 1];
$integerArray[$j + 1] = $integerArray[$j];
$integerArray[$j] = $Temp;
}
}
}
return $integerArray;
}

//result
0 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

冒泡是挺简单的,就是比较一趟趟比较,最坏的情况下时间复杂度是n的平方。快排则是在冒泡上改进的,将一趟排序的结果分两部分,一边的所有数据比另一边都要小,然后再对两个区域进行快排,其实就是递归

1
2
3
4
5
6
7
8
//同样,先生成一个乱序的数组,打印出来
$arr = range(0, 30);
shuffle($arr);
echo implode(" ", $arr);

//result
7 26 20 13 18 12 21 25 30 9 11 14 6 1 22 19 16 2 0 28 17 4 24 10 29 8 3 15 23 5
27

暂时拿这个当需要排序的数组:

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
//先生成一个乱序的数组
// $arr = range(0, 30);
// shuffle($arr);
$arr = explode(
" ",
"7 26 20 13 18 12 21 25 30 9 11 14 6 1 22 19 16 2 0 28 17 4 24 10 29 8 3 15 23 5 27");

function QuickSort($integerArray) {

}

function QuickSortCore($integerArray, $start, $end) {
$Temp = $integerArray[$start];
while ($start < $end){
while ($integerArray[$end] >= $Temp) {
$end--;
}
$integerArray[$start] = $integerArray[$end];
while ($integerArray[$start] <= $Temp && $start < $end) {
$start++;
}
$integerArray[$end] = $integerArray[$start];
}
$integerArray[$start] = $Temp;

return $integerArray;
}

echo
"7 26 20 13 18 12 21 25 30 9 11 14 6 1 22 19 16 2 0 28 17 4 24 10 29 8 3 15 23 5 27",
"\n";
echo implode(" ", QuickSortCore($arr, 0, sizeof($arr) -1));

这个就是快排的核心,首先要把start拿出来,挖个坑出来,然后拿跟end比较,把数组右侧比较小的数给弄到左边来,把数组左侧比较大的数弄右边去。其实就是个双端操作的冒泡。然后就是递归:

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
33
34
35
36
37
38
39
40
//成一个乱序的数组
$arr = range(0, 30);
shuffle($arr);

function Sorts($integerArray) {
QuickSort($integerArray, 0, sizeof($integerArray) - 1);
return $integerArray;
}

function QuickSort(&$integerArray, $start, $end) {
//递归结束条件
if ($start >= $end) {
return ;
}
//分区域后的返回值
$middleIndex = QuickSortCore($integerArray, $start, $end);
//递归调用
QuickSort($integerArray, 0, $middleIndex -1);
QuickSort($integerArray, $middleIndex + 1, $end);
}

function QuickSortCore(&$integerArray, $start, $end) {
$Temp = $integerArray[$start];
while ($start < $end){
while ($integerArray[$end] >= $Temp && $start < $end) {
$end--;
}
$integerArray[$start] = $integerArray[$end];
while ($integerArray[$start] <= $Temp && $start < $end) {
$start++;
}
$integerArray[$end] = $integerArray[$start];
}
$integerArray[$start] = $Temp;

return $start;
}

echo implode(" ", $arr), "\n";
echo implode(" ", Sorts($arr));

实际上当随机数比较大的时候,PHP会很慢,倒不如用PHP自带的sort()方法,这里只是学习一下快排的思想。