#include <iostream>
using namespace std;

//输出过程
void Print(int *A, int len)
{
	for(int i = 0; i < len; i++)
	{
		if(i)cout<<' ';
		else cout<<"==> A = {";
		cout<<A[i];
	}
	cout<<'}'<<endl;
}

/************************7.1普通快排************************************************/
//划分
int Partition(int *A, int p, int r)
{
	//选择A[r]作为主元
	int x = A[r];
	int i = p - 1, j;
	for(j = p; j < r; j++)
	{
		//小于主元的放在左边
		if(A[j] <= x)
		{
			i++;
			//把大于主元的交换到右边
			swap(A[i],A[j]);
		}
	}
	swap(A[i+1], A[r]);
	//返回最终主元的位置
	return i+1;
}

void QuickSort(int *A, int p, int r)
{
	if(p < r)
	{
		//以某个主元为标准，把数组分为两部分，左边都比主元小，右边都比主元大
		int q = Partition(A, p, r);
		//分别对左边和右边排序
		QuickSort(A, p, q-1);
		QuickSort(A, q+1, r);
	}
}

/********************7.3随机快排******************************************************/
//划分
int Randomized_Partition(int *A, int p , int r)
{
	//随机选择一个数作为主元
	int i = rand() % (r-p+1) + p;
	swap(A[r], A[i]);
	return Partition(A, p, r);
}
//排序，原理与普通快排相同，只是调用的划分方法不同
void Randomized_QuickSort(int *A, int p, int r)
{
	if(p < r)
	{
		int q = Randomized_Partition(A, p, r);
		Randomized_QuickSort(A, p, q-1);
		Randomized_QuickSort(A, q+1, r);
	}
}

7.1-1
    A = {13 19 9 5 12 8 7 4 21 2 6 11}
==> A = {9 5 8 7 4 2 6 11 21 13 19 12}
==> A = {5 4 2 6 9 8 7 11 21 13 19 12}
==> A = {2 4 5 6 9 8 7 11 21 13 19 12}
==> A = {2 4 5 6 9 8 7 11 21 13 19 12}
==> A = {2 4 5 6 7 8 9 11 21 13 19 12}
==> A = {2 4 5 6 7 8 9 11 21 13 19 12}
==> A = {2 4 5 6 7 8 9 11 12 13 19 21}
==> A = {2 4 5 6 7 8 9 11 12 13 19 21}
==> A = {2 4 5 6 7 8 9 11 12 13 19 21}
7.1-2
返回r
7.1-2
修改PARTITION(A, p, r)，增加对A[i]==x时的处理。对于A[i]==x的数据，一半放在x左边，一半放在x右边
//划分
int Partition(int *A, int p, int r)
{
	//选择A[r]作为主元
	int x = A[r];
	int i = p - 1, j;
	bool flag = 0;
	for(j = p; j < r; j++)
	{
		//小于主元的放在左边
		if(A[j] < x || (A[j] == x && flag))
		{
			i++;
			//把大于主元的交换到右边
			swap(A[i],A[j]);
			if(A[j] == x)flag = !flag;
		}
	}
	swap(A[i+1], A[r]);
	//返回最终主元的位置
	return i+1;
}
7.1-4
修改PARTITION(A, p, r)，把L4改为do if A[j] >= x

7.2-2
O(n^2)
7.2-4
基本有序的数列用快排效率较低

7.3-1
随机化不是为了提高最坏情况的性能，而是使最坏情况尽量少出现
7.3-2
最坏情况下，n个元素每次都划分成n-1和1个，1个不用再划分，所以O(n)次
最好情况下，每次从中间划分，递推式N(n)=1+2*N(n/2)=O(n)

7.4-5
//7.4-5利用插入排序改善快排
int k = 4;
//划分
int Partition(int *A, int p, int r)
{
	//选择A[r]作为主元
	int x = A[r];
	int i = p - 1, j;
	bool flag = 0;
	for(j = p; j < r; j++)
	{
		//小于主元的放在左边
		if(A[j] < x || (A[j] == x && flag))
		{
			i++;
			//把大于主元的交换到右边
			swap(A[i],A[j]);
			if(A[j] == x)flag = !flag;
		}
	}
	swap(A[i+1], A[r]);
	//返回最终主元的位置
	return i+1;
}
//快速排序
void QuickSort(int *A, int p, int r)
{
	//长度小于k的子数组不排序
	if(r - p >= k)
	{
		//以某个主元为标准，把数组分为两部分，左边都比主元小，右边都比主元大
		int q = Partition(A, p, r);
		//分别对左边和右边排序
		QuickSort(A, p, q-1);
		QuickSort(A, q+1, r);
	}
}
//插入排序
void InsertSort(int *A, int p, int r)
{
	int i, j;
	for(i = p + 1; i <= r; i++)
	{
		int temp = A[i];
		j = i;
		while(A[j-1] > temp)
		{
			A[j] = A[j-1];
			j--;
		}
		A[j] = temp;
	}
}
void Sort(int *A, int p, int r)
{
	//先进行粗粒度的快排
	QuickSort(A, p, r);
	//逐个进行插入排序
	InsertSort(A, p, r);
}

a）
    A = {13 19 9 5 12 8 7 4 11 2 6 21}  
==> A = {6 19 9 5 12 8 7 4 11 2 13 21}  
==> A = {6 2 9 5 12 8 7 4 11 19 13 21}  
==> A = {4 2 9 5 12 8 7 6 11 19 13 21}  
==> A = {4 2 5 9 12 8 7 6 11 19 13 21}  
==> A = {2 4 5 9 12 8 7 6 11 19 13 21}  
==> A = {2 4 5 6 12 8 7 9 11 19 13 21}  
==> A = {2 4 5 6 7 8 12 9 11 19 13 21}  
==> A = {2 4 5 6 7 8 9 12 11 19 13 21}  
==> A = {2 4 5 6 7 8 9 12 11 13 19 21}
b）
int Hoare_Partition(int *A, int p, int r)  
{  
    int x = A[p], i = p - 1, j = r + 1;  
    while(true)  
    {  
        do{j--;}  
        while(A[j] > x);  
        do{i++;}  
        while(A[i] < x);  
        if(i < j)  
            swap(A[i], A[j]);  
        else return j;  
        Print(A, 12);  
    }  
}  
void Hoare_QuickSort(int  *A, int p, int r)  
{  
    if(p < r)  
    {  
        int q = Hoare_Partition(A, p, r);  
        Hoare_QuickSort(A, p, q-1);  
        Hoare_QuickSort(A, q+1, r);  
    }  
}

void Stooge_Sort(int *A, int i, int j)  
{  
    if(A[i] > A[j])  
        swap(A[i], A[j]);  
    if(i + 1 >= j)  
        return;  
    k = (j - i + 1) / 3;  
    Stooge_Sort(A, i, j-k);  
    Stooge_Sort(A, i+k, j);  
    Stooge_Sort(A, i, j-k);  
}
以下内容转http://blog.csdn.net/zhanglei8893
a）对于数组A[i...j]，STOOGE-SORT算法将这个数组划分成均等的3份，分别用A, B, C表示。
     第6-8步类似于冒泡排序的思想。它进行了两趟：
     第一趟的第6-7步将最大的1/3部分交换到C
     第二趟的第8步将除C外的最大的1/3部分交换到B
     剩余的1/3位于A，这样的话整个数组A[i...j]就有序了。
b）比较容易写出STOOGE-SORT最坏情况下的运行时间的递归式
           T(n) = 2T(2n/3)+Θ(1)
     由主定律可以求得T(n)=n^2.71
c）各种排序算法在最坏情况下的运行时间分别为：
    插入排序、快速排序：Θ(n^2)
    堆排序、合并排序：Θ(nlgn)
    相比于经典的排序算法，STOOGE-SORT算法具有非常差的性能，这几位终生教授只能说是浪得虚名了^_^

a)
void QuickSort2(int *A, int p, int r)
{
	while(p < r)
	{
		int q = Partition(A, int p, r);
		QuickSort2(A, p, q-1);
		p = q + 1;
	}
}

b)
A = {1, 2, 3, 4, 5, 6}
c)
void QuickSort3(int *A, int p, int r)
{
	while(p < r)
	{
		int q = Partition(A, int p, r);
		if(r-q > q-p)
		{
			QuickSort3(A, p, q-1);
			p = q + 1;
		}
		else
		{
			QuickSort3(A, q+1, r);
			r = q - 1;
		}
	}
}

7-5 “三数取中”划分

//三数取中
int GetMid(int *A, int p, int r)
{
	int a = -1, b = -1, c = -1;
	while(a < p)a = rand() % (r+1);
	while(b < p)b = rand() % (r+1);
	while(c < p)c = rand() % (r+1);
	if((A[a]-A[b])*(A[a]-A[c])<=0)return a;
	if((A[b]-A[a])*(A[b]-A[c])<=0)return b;
	if((A[c]-A[a])*(A[c]-A[b])<=0)return c;
}
//划分
int Partition(int *A, int p, int r)
{
	//选择A[r]作为主元
	int m = GetMid(A, p , r);
	swap(A[m], A[r]);
	int x = A[r];
	int i = p - 1, j;
	bool flag = 0;
	for(j = p; j < r; j++)
	{
		//小于主元的放在左边
		if(A[j] < x || (A[j] == x && flag))
		{
			i++;
			//把大于主元的交换到右边
			swap(A[i],A[j]);
			if(A[j] == x)flag = !flag;
		}
	}
	swap(A[i+1], A[r]);
	//返回最终主元的位置
	return i+1;
}
//快速排序
void QuickSort(int *A, int p, int r)
{
	//长度小于k的子数组不排序
	if(r > p)
	{
		//以某个主元为标准，把数组分为两部分，左边都比主元小，右边都比主元大
		int q = Partition(A, p, r);
		//分别对左边和右边排序
		QuickSort(A, p, q-1);
		QuickSort(A, q+1, r);
	}
}