曾经在一次面试中，面试官问过我这个算法，我当时一脸懵逼，就说它比较快，所以就是快速排序，至于怎么快的一问三不知。所谓吃一堑长一智嘛，不管你怎么理解，最终还不得反应到代码实现上么？不费话了，上代码。
概念
快速排序 - Quick Sort：又称划分交换排序 - partition-exchange sort，简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n^2) 次比较，但这种状况并不常见。事实上，快速排序 O(n log n) 通常明显比其他算法更快，因为它的内部循环 （inner loop）可以在大部分的架构上很有效率地达成。
步骤
- 从数列中挑出一个元素，称为『基准』-
pivot - 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（
partition）操作 - 递归地（
recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序
实现
方案一
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| <?php
class QuickSort
{
/**
* 主运行方法
*
* @return void
*/
public static function main(): void
{
$random = self::random();
$array = self::sort($random);
print_r($array);
}
/**
* 快速排序
*
* @param array $array
*
* @return array
*/
public static function sort(array &$array): array
{
$count = count($array);
if ($count <= 1) {
return $array;
}
$pivot = $array[0]; // 取数组第一个元素为基准值
$left = $right = [];
for ($i = 1; $i < $count; $i++) {
$value = $array[$i];
if (self::compare($pivot, $value) > 0) {
$left[] = $array[$i];
} else {
$right[] = $array[$i];
}
}
$left = self::sort($left);
$right = self::sort($right);
return array_merge($left, (array)$pivot, $right);
}
/**
* 比较大小
*
* @param int $x
* @param int $y
*
* @return int
*/
private static function compare(int $x, int $y): int
{
return $x <=> $y;
}
/**
* 互换位置
*
* @param int $x
* @param int $y
*
* @return void
*/
private static function swap(int &$x, int &$y): void
{
if ($x !== $y) {
$t = $x;
$x = $y;
$y = $t;
}
}
/**
* 生成随机数组
*
* @param int $low
* @param int $high
* @param int $num
*
* @return array
*/
private static function random(int $low = 1, int $high = 9999, int $num = 10): array
{
$num = $num > $high ? $high : $num;
$range = range($low, $high);
$array = array_rand(array_flip($range), $num);
shuffle($array);
return $array;
}
}
QuickSort::main();
// 结果
Array
(
[0] => 1073
[1] => 1535
[2] => 3376
[3] => 3702
[4] => 3961
[5] => 4139
[6] => 4644
[7] => 5032
[8] => 5803
[9] => 6450
)
|
方案二
使用 Lomuto partition scheme 方式
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| <?php
class QuickSort
{
/**
* 主运行方法
*
* @return void
*/
public static function main(): void
{
$random = self::random();
$array = self::sort($random, 0, count($random) - 1);
print_r($array);
}
/**
* 快速排序
*
* @param array $array
* @param int $low
* @param int $high
*
* @return array
*/
public static function sort(array &$array, int $low, int $high): array
{
if ($low < $high) {
$index = self::partition($array, $low, $high);
self::sort($array, $low, $index - 1);
self::sort($array, $index + 1, $high);
}
return $array;
}
/**
* 原地分区
*
* @param array $array
* @param int $low
* @param int $high
*
* @return int
*/
private static function partition(array &$array, int $low, int $high): int
{
$pivot = $array[$high]; // 选取最右边的元素为基准
$i = $low - 1;
for ($j = $low; $j < $high; $j++) {
if (self::compare($pivot, $array[$j]) > 0) {
$i++;
self::swap($array[$i], $array[$j]);
}
}
self::swap($array[$i + 1], $array[$high]);
return $i + 1;
}
/**
* 比较大小
*
* @param int $x
* @param int $y
*
* @return int
*/
private static function compare(int $x, int $y): int
{
return $x <=> $y;
}
/**
* 互换位置
*
* @param int $x
* @param int $y
*
* @return void
*/
private static function swap(int &$x, int &$y): void
{
if ($x !== $y) {
$t = $x;
$x = $y;
$y = $t;
}
}
/**
* 生成随机数组
*
* @param int $low
* @param int $high
* @param int $num
*
* @return array
*/
private static function random(int $low = 1, int $high = 9999, int $num = 10): array
{
$num = $num > $high ? $high : $num;
$range = range($low, $high);
$array = array_rand(array_flip($range), $num);
shuffle($array);
return $array;
}
}
QuickSort::main();
// 结果
Array
(
[0] => 1411
[1] => 3434
[2] => 3776
[3] => 6020
[4] => 6047
[5] => 6367
[6] => 7107
[7] => 7783
[8] => 9135
[9] => 9248
)
|
方案三
使用 Hoare partition scheme 方式
未完待续…