快速排序（Quick Sort）是对冒泡排序的一种改进，属不稳定排序算法，由东尼·霍尔在1962年提出。快速排序基本步骤：从数列中挑出一个元素（一般称为称为“基准”），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比基准小，另外一部分的所有数据都比基准大，与基准相等的数据可放在两部分中的任一部分，然后再按此方法递归地对这两部分数据分别进行处理，以达到整个数据变成有序序列。快速排序，最好情况下，时间复杂度为O(nlogn)；最坏情况下，时间复杂度为O(n2)；平均时间复杂度为O(nlogn)。
快速排序示例图：
|
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
|
<?php/** * 数据结构与算法（PHP实现） - 快速排序（Quick Sort）。 * * @author 创想编程（TOPPHP.ORG） * @copyright Copyright (c) 2013 创想编程（TOPPHP.ORG） All Rights Reserved * @license http://www.opensource.org/licenses/mit-license.php MIT LICENSE * @version 1.0.0 - Build20130614 */class /** * 需要排序的数据数组。 * * @var array */ private$data; /** * 数据数组的长度。 * * @var integer */ private$size; /** * 数据数组是否已排序。 * * @var boolean */ private$done; /** * 构造方法 - 初始化数据。 * * @param array $data 需要排序的数据数组。 */ publicfunction __construct(array$data) { $this->data =$data; $this->size =count($this->data); $this->done = FALSE; } /** * 交换数据数组中两个元素的位置。 * * @param integer $x 元素在数组中的索引。 * @param integer $y 元素在数组中的索引。 */ privatefunction swap($x,$y) { $temp= $this->data[$x]; $this->data[$x] =$this->data[$y]; $this->data[$y] =$temp; } /** * 快速排序。 * * @param integer $left 数组第一个元素索引。 * @param integer $right 数组最后一个元素索引。 */ privatefunction sort($left,$right) { if($left $right) { return; } $pivot= $this->data[$left]; $start= $left; $end= $right; while($start $end) { while($start $end && $this->data[$end] >=$pivot) { --$end; } $this->swap($start,$end); while($start $end && $this->data[$start] <$pivot) { ++$start; } $this->swap($start,$end); } $this->sort($left,$start - 1); $this->sort($start+ 1, $right); } /** * 获取排序后的数据数组。 * * @return array 返回排序后的数据数组。 */ publicfunction getResult() { if($this->done) { return$this->data; } $this->sort(0,$this->size - 1); $this->done = TRUE; return$this->data; }}?> |
|
1
2
3
4
|
<?php$quick new QuickSort(array(5, 3, 8, 9, 6, 2));echo , print_r($quick->getResult(), TRUE),'</pre>';?> |