7.4-5 快速排序+插入排序
粗略证明如下：
从书中证明可知，只要划分是常数比，那么最后期望都是一样的。故假设每次划分都是均匀的。假设划分深度为h时，每个块的规模都不超过k，则有k*2^h = n，h = lg(n/k)。又因为在最底层，规模不超过k的子序列有n/k个，所以每个子序列内部插入排序时间为O(k^2)，总的插入排序时间为O(nk)。(注意：这一步证明不严格，每个都是O(K^2)，加起来可能比O(nk)要大。)
每一次划分为O(n)，总共有lg(n/k)层，所以划分的复杂度为O(nlg(n/k))，所以，总的时间为O(nk + nlg(n/k))。
7-4 快速排序的堆栈深度
优化的尾递归：
QUICKSORT (A, p, r )
while p <
r
do Partition and sort the small
subarray Trst
q ← PARTITION(A, p, r
)
if q ? p < r ?
q
then QUICKSORT (A,
p, q ? 1)
p ← q + 1
else QUICKSORT (A, q + 1, r )
r ←
q ? 1
7-6 模糊排序
快速排序可以看成区间大小为1的模糊排序。模糊排序的关键在于如何充分利用重叠区间，解决思路是在调用Partion()划分时，区间如果重叠的部分，就把它们看做是相等的，并提取公共部分继续划分。
转载代码来源http://blog.csdn.net/mishifangxiangdefeng/article/details/7681109
|
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
128
129
130
131
132
133
134
135
136 |
#include <iostream>using
namespace std;struct
node{ int
start; int
end; bool
operator<(const
node & b)const { return
end < b.start; } bool
operator==(const
node & b)const { return
(end >= b .start) && (start <= b.end); } bool
operator>(const
node & b)const { return
start > b.end; }};//划分结果：0 -> a小于主元，a+1 -> b-1等于主元，b -> length_A大于主元struct
divid{ int
a; int
b;};node A[11];int
length_A = 10;//按划分结果分三行显示void
Print(divid d){ int
i = 1; if(d.a > 0) { for(i = 1; i <= d.a; i++) cout<<‘(‘<<A[i].start<<‘,‘<<A[i].end<<") "; cout<<endl; i = d.a + 1; } if(d.b > 0) { for(; i < d.b; i++) cout<<‘(‘<<A[i].start<<‘,‘<<A[i].end<<") "; cout<<endl; i = d.b; } if(i <= length_A) { for(; i <= length_A; i++) cout<<‘(‘<<A[i].start<<‘,‘<<A[i].end<<") "; cout<<endl; } cout<<endl;}//交换void
Exchange(node &a, node &b){ node temp; temp = a; a = b; b = temp;}//划分是重点divid Partition(node *A, int
p, int
r){ //先取任意一个元素为主元 node x = A[r]; int
i = p-1, j = r+1, k = p; while(k <=r && k < j) { //如果小于主元，交换到前面 if(A[k] < x) { i++; Exchange(A[i], A[k]); k++; } //如果大于，交换到后面 else
if(A[k] > x) { j--; Exchange(A[j], A[k]); //这里不能k++，因为交换过来的元素也可能大于主元 } else { //如果相等，不交换，但是要提取公因子 x.end = min(x.end, A[k].end); x.start = max(x.start, A[k].start); k++; } } //返回划分结果 divid ret = {i, j}; if(ret.a < p)ret.a = -1; if(ret.b > r)ret.b = -1; Print(ret); return
ret;}void
QuickSort(node *A, int
p, int
r){ if(p >= r) return; //把数组划分为三段 divid q = Partition(A, p, r); //如果存在第一段，对第一段排序 if(q.a > 0) QuickSort(A, p, q.a); //如果存在第三段，对第三段排序 if(q.b > 0) QuickSort(A, q.b, r);}int
main(){ int
i, n; cin>>n; length_A = n; //init data by random for(i = 1; i <= length_A; i++) { A[i].start = rand() % 100; A[i].end = rand() % 100; if(A[i].start > A[i].end) swap(A[i].start, A[i].end); } divid d = {-1, -1}; Print(d); //sort QuickSort(A, 1, length_A); return
0;} |
原文：http://www.cnblogs.com/rolling-stone/p/3653045.html