快速排序基本特性
- 时间复杂度：O（n*lgn）
- 最坏：O（n^2）
- 空间复杂度：最好情况下：O（lgn），最坏情况：O(n)，平均情况：O(lgn)
- 不稳定。
关于快速排序的空间复杂度，谢谢@命运他爹 同学指正。详述一下。
快速排序由于每次递归的时候会占用一个空间返回中间数位置，所以一次递归的空间复杂度为O(1)。
最好情况和平均情况下的递归深度为O(lgn)，相应的空间复杂度就是O(lgn)
最坏情况下的递归深度为O(n)，空间复杂度为O(n)。
算法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
QUICKSORT(A, p, r) if
p < r
then q ← PARTITION(A, p, r) //关键
QUICKSORT(A, p, q - 1)
QUICKSORT(A, q + 1, r)
PARTITION(A, p, r) x ← A[r]
i ← p - 1
for
j ← p to r - 1
do
if A[j] ≤ x
then i ← i + 1
exchange A[i] <-> A[j]
exchange A[i + 1] <-> A[r]
return
i + 1
|
示例
待排序数组：7 3 5 9 8 5 1 10 4 6
一趟排序过程分析：
源码
类声明
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class
BaseSort {
public:
BaseSort() { }
virtual
void sort() = 0;
};class
QuickSort : public
BaseSort {
public:
QuickSort(int
Array[], int
len) : BaseSort() {
this->Array = Array;
this->len = len;
}
void
sort();
private:
int
partition(int
Array[], int
start, int
end);
void
quicksort(int
Array[], int
start, int
end);
private:
int* Array;
int
len;
}; |
相关成员函数实现
|
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
|
void
QuickSort::sort() {
quicksort(Array, 0, len-1);
}void
QuickSort::quicksort(int
Array[], int
start, int
end) {
if
( start < end ) {
int
mid = this->partition(Array, start, end);
if
( start < mid - 1 )
quicksort(Array, start, mid-1 );
if
( mid + 1 < end )
quicksort(Array, mid+1, end);
}
}int
QuickSort::partition(int
Array[], int
start, int
end) {
int
i, j, x, tmp;
x = Array[end];
i = start -1;
for
( j = start; j < end; j++ ) {
if
( Array[j] <= x) {
i++;
tmp = Array[j];
Array[j] = Array[i];
Array[i] = tmp;
}
}
tmp = Array[end];
Array[end] = Array[i+1];
Array[i+1] = tmp;
if
(DEBUG) {
printArray(Array, len, "MidResult");
}
return
i+1;
} |
测试：
|
1
2
3
4
5
6
|
int a[10] = {7,3,2,9,8,5,1,10,4,6};
int len = 10;
QuickSort* quicksort= new
QuickSort(a, len);
quicksort->sort();printArray(a, len, "QuickSort");
|
运行截图：
参考资料：
《算法导论 2rd》