简介
复杂度分析： 期望复杂度 O(n lg n) 最坏复杂度 O(n^2)
数组 A[p.. r] 被划分为两个（可能为空）子数组 A[p.. q-1] A[q+ 1.. r], 使得
A[p .. l] 中的每一个元素都小于等于 A[q], A[q] 也小于等于 A[q+l..r] 中的每个元素。
其中，计算下标 也是划分过程的一部分。
源码
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
| #include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int partition(int *A, int p, int r) {
int x = A[r];
int i = p - 1;
for (int j = p; j <= r - 1; j++) {
if (A[j] <= x) {
++i;
std::swap(A[i], A[j]);
}
}
std::swap(A[i + 1], A[r]);
return i + 1;
}
void quick_sort(int *A, int p, int r) {
if (p < r) {
int q = partition(A, p, r);
quick_sort(A, p, q - 1);
quick_sort(A, q + 1, r);
}
}
int main(int argn, char *argc[]) {
srand((unsigned)time(0));
const int MAX_ARRAY = 10;
const int NUMBER_RANGE = 500;
int *A = new int[MAX_ARRAY];
for (int i = 0; i < MAX_ARRAY; i++) {
A[i] = rand() % NUMBER_RANGE;
}
for (int i = 0; i < MAX_ARRAY; i++) {
std::cout << A[i] << " ";
}
std::cout << std::endl << "--------------" << std::endl;
quick_sort(A,0,MAX_ARRAY-1);
for (int i = 0; i < MAX_ARRAY; i++) {
std::cout << A[i] << " ";
}
std::cout << std::endl;
delete [] A;
}
|
调试分析
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
|
输入随机串：
404 411 300 143 462 12 455 288 142 118
^ ^ ^
i j r
开始：
i=-1 j=0 r=9
404 411 300 143 462 12 455 288 142 118
^ ^ ^
i j r
i=-1 j=5 r=9 找出来了，将 i++并且将 i=0 j=5 交换
12 411 300 143 462 404 455 288 142 118
^ ^ ^
i j r
i=0 j=8 r=9
一直到j贴近r了，都没有找出比r小的数据。
将i+1位置和r位置交换。
这样就满足了以i+1位置为中线，左侧数字都比它小，右侧都比它大；
并且返回i+1作为分而治之的两块接着交给后续函数完成递归排序。
12 118 300 143 462 404 455 288 142 411
^ ^ ^
i+1 j r
i=0 j=8 r=9
递归算法将刚刚的返回值i+1当成q，以这个为分隔切开两个数组接着交给
下一轮递归排序来跑。
1. 前面的分隔的数组
s=0,r=q-1
[12] 118 300 143 462 404 455 288 142 411
^
q
2. 后面的分隔的数组
s=q+1,r=r
12 118 [300 143 462 404 455 288 142 411]
^
q
递归下去的算法，又是一个轮回。找到最后一个数字，并且将前面的全部数字
按照左小，右大的方式破开，然后再次来分而治之来处理。
300 143 462 404 455 288 142 411
^ ^ ^
i j r
143 300 462 404 455 288 142 411
^ ^ ^
i j r
143 300 404 462 455 288 142 411
^ ^ ^
i j r
143 300 404 462 455 288 142 411
^ ^ ^
i j r
143 300 404 288 455 462 142 411
^ ^ ^
i j r
143 300 404 288 455 462 142 411
^ ^ ^
i j r
143 300 404 288 142 462 455 411
^ ^ ^
i j r
143 300 404 288 142 462 455 411
^ ^ ^
i+1 j r
最终排序的情况
143 300 404 288 142 411 455 462
^
q
|
复杂度分析
算法复杂度位于： O(nlgn)~O(nn)。
快排本质上是一个递归二叉树，而且每次树里面都有固定要有n次，所以最凑巧的时候，这棵二叉树是
平衡的，树的高度为 lgn ，最不凑巧的情况就是这棵树一直都偏为一边，这样高度就和 n 相同。
1
2
3
4
5
6
7
|
1
/ \
2 3
/ \ / \
4 5 6 7
|