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 Þrst
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
#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 randomfor(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);//sortQuickSort(A, 1, length_A);return 0;
}