温故知新：快速排序算法(quick sort)及优化

快速排序

快速排序算法的基本思想是在数组a[0~n]中找一个元素a[r]作为划分点，在a[r]右边的数组都小于该划分点，在a[r]左侧的数组都大于该划分点，然后再在a[0~r-1]和a[r+1~n]重复该步骤。

template<typename T>
void quickSort_plus(T a[],int l,int r){
        if(l>=r) return ;
	T v=a[r];
	int left=l-1;
	int right=r;
	while(1){
		while(a[++left]<v) ;
		while(a[--right]>v && right<left) ;
		if(right>=left) break;
		swap(a[left],a[right]);
	}
	swap(a[left],a[r]);
	if(left-l<r-left) {quickSor_plust(a,l,left-1);quickSort_plus(a,left+1,r);}
	else {quickSort_plus(a,left+1,r);quickSort_plus(a,l,left-1);}
}

对于每次划分时若是均匀划分，即对半划分，则快速排序运行时间达到最短o(nlogn)，若每次划分都是右边只有一个元素左边有n-1个元素，则快速排序达到了最糟糕的情况，时间复杂度为o(n*n)。所以为了尽量地缩短时间，每次递归时都优先考虑较短的那一边先递归。

也可以用rand()函数来选择划分点，使划分结果的期望接近于均匀划分，实现程序为

template<typename T>
void randomQuickSort(T a[],int l,int r)
{
    if(l>=r) return ;

    int i=rand()%(r-l+1)+l;
    swap(a[i],a[r]);

    T v=a[r];
    int left=l-1,right=r;
    while(1)
    {
        while(a[++left]<v) ;
        while(a[--right]>v && right>left) ;
        if(right<=left) break;
        swap(a[left],a[right]);
    }
    swap(a[left],a[r]);
    if(r-left>left-l) {randomQuickSort(a,l,left-1);randomQuickSort(a,left+1,r);}
    else {randomQuickSort(a,left+1,r);randomQuickSort(a,l,left-1);}
}

还有一个办法就是三数取中，就是在a[l],a[(l+r)/2],a[r]中取中间数作为划分点.

template<typename T>
void quickSort_mid(T a[],int l,int r)
{
    if(r-l<=0) return;

    int mid=(l+r)/2;
    if(a[l]>a[mid]) swap(a[l],a[mid]);
    if(a[l]>a[r]) swap(a[l],a[r]);
    if(a[mid]>a[r]) swap(a[mid],a[r]);
    swap(a[r-1],a[mid]);

    T v=a[r-1];
    int left=l,right=r-1;
    while(1)
    {
        while(a[++left]<v) ;
        while(a[--right]>v && right>left) ;
        if(right<=left) break;
        swap(a[left],a[right]);
    }
    swap(a[left],a[r-1]);
    if(r-left>left-l) {quickSort_mid(a,l,left-1);quickSort_mid(a,left+1,r);}
    else {quickSort_mid(a,left+1,r);quickSort_mid(a,l,left-1);}
}

三数取中的快排比原版快排及随机快排的效果都来的好。

非递归快速排序

在糟糕的情况下快速排序可能要消耗o(n)的栈空间，可以采用stack来模拟递归，以减少栈空间的消耗。

template<typename T>
void nonrecursionQuickSort(T a[],int l,int r)
{
    stack<int> s;
    s.push(r);
    s.push(l);
    while(!s.empty())
    {
        l=s.top();
        s.pop();
        r=s.top();
        s.pop();
        if(l>=r) continue;
        T v=a[r];
        int left=l-1;
        int right=r;
        while(1)
        {
            while(a[++left]<v) ;
            while(a[--right]>v && left<right) ;
            if(right<=left) break;
            swap(a[left],a[right]);
        }
        swap(a[left],a[r]);
        if(r-left>left-l) {s.push(r);s.push(left+1);s.push(left-1);s.push(l);}
        else {s.push(left-1);s.push(l);s.push(r);s.push(left+1);}
    }
}

三划分快速排序

对于所给的数组中可能会存在重复的数字。我们在每次递归时将与划分点相同的元素放在一起，并且这些数组不参与下一次的递归，具体如下，假如a[v]为划分点，那么在进行划分时，将和a[v]相同的元素放在数组两头，在划分完成后在将这些重复的元素放置在划分点左右构成第三个区间，然后对该区间右边的数组和左边的数组进行递归，程序如下，

template<typename T>
void threePartitionQuickSort(T a[],int l,int r){
	if(l>=r) return ;
	T v=a[r];
	int left=l-1;
	int right=r;
	int q=l-1;
	int p=r;
	while(1){
		while(a[++left]<v) ;
		while(a[--right]>=v && right<left) ;
		if(left>=right) break;
		swap(a[left],a[right]);
        if(a[left]==v) swap(a[++q],a[left]);
        if(a[right]==v) swap(a[--p],a[right]);
	}
	swap(a[left],a[r]);
	for(int i=l,j=left-1;i<q;i++,j--) swap(a[i],a[j]);
	for(int i=r,j=left+1;i>p;i--,j++) swap(a[i],a[j]);
	if(left-l<r-left) {threePartitionQuickSort(a,l,left-1);threePartitionQuickSort(a,left+1,r);}
	else {threePartitionQuickSort(a,left+1,r);threePartitionQuickSort(a,l,left-1);}
}

可以看到当数组中没有重复元素时，上面程序和原版的快排是没有区别的，可见上面的程序包括了原版的快排。

快速排序和插入排序

插入排序的时间复杂度为o(n*n)，但是当要排序的数组并不是很混乱时，插入排序可以发挥很大用处。我们知道快排是递归函数，在执行快排时不断地递归大量小数组，那么就可以在当要递归的数组达到一定小时，便停止递归，这样最后得到了一个有一定秩序的数组，再调用插入排序即可。这样效率有很大的提升。

template<typename T>
void insertion(T a[],int l,int r)
{
    for(int i=l+1;i<=r;i++)
    {
        T v=a[i];
        int j=i;
        while(j>l && v<a[j-1])
        {
            a[j]=a[j-1];
            j--;
        }
        a[j]=v;
    }
}
template<typename T>
void quickSort_M(T a[],int l,int r)
{
    if(r-l<M) return;
    T v=a[r];
    int left=l-1,right=r;
    while(1)
    {
        while(a[++left]<v) ;
        while(a[--right]>v && right>left) ;
        if(right<=left) break;
        swap(a[left],a[right]);
    }
    swap(a[left],a[r]);//a[left] must be more than a[r]
    if(r-left>left-l){quickSort_M(a,l,left-1);quickSort_M(a,left+1,r);}
    else {quickSort_M(a,left+1,r);quickSort_M(a,l,left-1);}
}
template<typename T>
void Sort(T a[],int l,int r)
{
    quickSort_M(a,l,r);
    insertion(a,l,r);
}

各个快速排序的比较结果如下：