主要事如何划分再排序，使用递归方法，即创建两个函数，一个划分，一个排序。
划分伪代码：1
2
3
4
5
6
7
8
9
10
11
12i = low
x = A[low]
for j=low+1 to high
if A[j] <= x then
i = i+1
if i != j then
swap(a[i], a[j])
end if
end for
swap(a[low], a[i])
w = i;
return A和w
复杂度分析：
快速排序算法的时间复杂度为O(nlogn)。就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为log2n，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)。
完整代码：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#include <iostream>
#include <algorithm>
using namespace std;
int partion(int a[], int low, int high)
{
int l = low, temp = a[low], w = 0;
for(int i = low+1; i<high; i++)
{
//若是大于基准，则continue，即i往后移，若小于基准，则l后移，且若i不等于了，则交换a[i]和a[l]
if(a[i] <= temp)
{
l++;
if(l != i)
{
swap(a[i], a[l]);
}
}
}
swap(a[low], a[l]);
w = l;
return w;
}
void quick(int a[], int low, int high)
{
int w = 0;
if(low < high)
{
w = partion(a, low, high);
quick(a, low, w-1);
quick(a, w+1, high);
}
}
int main()
{
int a[8] = {5, 7, 1, 6, 4, 8, 3, 2};
int len = sizeof (a)/sizeof (a[0]);
quick(a, 0, len);
for(int i=0; i<len; i++)
{
cout << a[i] << ' ';
}
cout << endl;
return 0;
}
运行结果：
