算法导论学快排

前言

【算法导论描述】：快速排序在输入为n个数的数组，其最坏时间复杂度为$Θ(n^2)$，不过快速排序仍是实际排序应用中最好的选择，它的平均性能很好，期望时间复杂度为$Θ(nlgn)$，而且$Θ(nlgn)$中隐含的常数因子非常小，除此之外，快速排序很是一个能够进行原址排序的算法，不需要额外地申请空间，甚至在虚存环境也能很好地工作。

---

快速排序是采用分治策略的算法，有“分解”，”解决“，”合并“这三个过程，不过快速排序是进行原址排序的，因此不需要合并操作。

---

快排的关键点主要在于找那个划分点，你可以选择第一个，最后一个或者是随机选择一个作为划分点将数组划分为两个，一个小于等于划分点的值，另一个数组则反之。

---

快排C/C++实现

#include<cstdio>

void swap(int &a,int &b)
{
	int tmp=a;
	a=b;
	b=tmp;
}

int Partition(int A[],int L,int R)		//划分点选取最后一个
{
	int x=A[R];
	int i=L-1;
	for(int j=L;j<=R-1;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 Left,int Right)
{
	if(Left<Right)		//数组只剩下一个不需要再划分了 
	{
		int w=Partition(A,Left,Right);
		QuickSort(A,Left,w-1);
		QuickSort(A,w+1,Right);
	}
}

int main()
{
	int N;
	scanf("%d",&N); 
	int *A=new int[N];
	for(int i=0;i<N;++i)
		scanf("%d",&A[i]);
	QuickSort(A,0,N-1);
    for(int i=0;i<N;++i)
    {
        printf("%d",A[i]);
        if(i!=N-1)
            printf(" ");
    }
	return 0;	
} 

---

快速排序的性能

其性能（运行时间）取决于划分是否平衡，而平衡与否又主要依赖于用于划分的元素。如果划分是平衡的，那么快速排序算法性能与归并性能一样。如果划分是不平衡的，那么快速排序的性能会接近于插入排序。

---

最坏情况划分就是当输入数组是有序时，无论是递增还是递减，快速排序的时间复杂度此时都是$Θ(n^2)$，因为上面的练习已知划分算法Partition的时间复杂度为$Θ(n)$，所以当数组为有序时，QuickSort这个过程一共要去做n次的划分算法Partition，时间复杂度就会变成$Θ(n^2)$了，不过当数组为有序时，插入排序的时间复杂度为$Θ(n)$

---

最好情况划分

在可能的最平衡的划分中，Partition得到的两个子问题的规模都不大于n/2。这是因为其中一个子问题的规模为￥$\lfloor n/2\rfloor$，而另一个子问题的规模为$\lceil n/2\rceil-1$。在这种情况下，快排整体的性能非常好。此时，算法运行时间的递归式为：$T(n)=2T(n/2)+Θ(n)$，在这个式子中，忽略了一些余项以及减一操作的影响。根据主定理的情况2（树的总代价均匀分布在树的所有层次上），该递归式的解为$T(n)=Θ(nlgn)$。通过在每一层递归中都平衡地划分子数组，我们能得到一个渐进时间上更快地算法。

---

快速排序的随机化版本

C/C++版本

#include<cstdio>
#include<cstdlib>

void swap(int &a,int &b)
{
	int tmp=a;
	a=b;
	b=tmp;
}

int Partition(int A[],int L,int R)		//划分点选取最后一个
{
	int x=A[R];
	int i=L-1;
	for(int j=L;j<=R-1;j++)
	{
		if(A[j]<=x){
			i++;
			swap(A[i],A[j]);
		}
	}
	swap(A[i+1],A[R]);
	return i+1;
}

int Randomized_Partition(int A[],int L,int R)
{
	int i=rand()%(R-L+1)+L;
	swap(A[R],A[i]);
	return Partition(A,L,R);
}

void QuickSort(int A[],int Left,int Right)
{
	if(Left<Right)		//数组只剩下一个不需要再划分了 
	{
		int w=Randomized_Partition(A,Left,Right);
		QuickSort(A,Left,w-1);
		QuickSort(A,w+1,Right);
	}
}

int main()
{
	int N;
	scanf("%d",&N); 
	int *A=new int[N];
	for(int i=0;i<N;++i)
		scanf("%d",&A[i]);
	QuickSort(A,0,N-1);
    for(int i=0;i<N;++i)
    {
        printf("%d",A[i]);
        if(i!=N-1)
            printf(" ");
    }
	return 0;	
} 

这个版本的效率真的远超没有随机化去划分的做法。

---

求第k个小的数

快排，递归一部分，直至找到指定第k个小的数。时间复杂度为$Θ(n)$。

#include<cstdio>
#include<cstdlib>

void swap(int &a,int &b)
{
	int tmp=a;
	a=b;
	b=tmp;
}

int Partition(int A[],int L,int R)		
{
	int x=A[R];
	int i=L-1;
	for(int j=L;j<=R-1;j++)
	{
		if(A[j]<=x){
			i++;
			swap(A[i],A[j]);
		}
	}
	swap(A[i+1],A[R]);
	return i+1;
}

int Randomized_Partition(int A[],int L,int R)
{
	int i=rand()%(R-L+1)+L;
	swap(A[R],A[i]);
	return Partition(A,L,R);
}

int QuickSort(int A[],int Left,int Right,int k)
{
	if(Left<=Right)		
	{
		int w=Randomized_Partition(A,Left,Right);
		if(w==k-1)
			return A[w];
		else if(w>k-1)
			QuickSort(A,Left,w-1,k);
		else
			QuickSort(A,w+1,Right,k);
	}
}

int main()
{
	int N,k;
	scanf("%d %d",&N,&k); 
	int *A=new int[N];
	for(int i=0;i<N;++i)
		scanf("%d",&A[i]);
	printf("%d",QuickSort(A,0,N-1,k));
	return 0;	
}