快速排序和归并排序

快速排序和归并排序都是采用了分治法的策略

分治法是将大的问题逐渐分解成单位元素的问题，然后再从底层一个个子问题的合成为原来问题的解。能采用分治法的案例，子问题一定是互相独立的，即不存在重叠子问题。

1.快速排序

     目标：输入一个数组a[p:r],并通过基准元素a[t](p<t<r)在a[p:t-1]中找到比a[t]小的元素和在a[t+1:r]中找到比a[t]大的元素，并按照顺序排列大小，即a[p:t-1]中的小者，a[t],a[t+1:r]中的大者。一般我们选用基准元素a[p],经过不停的查找就可以使得排序完成。

 

 

 

 

 

 

 

算法的时间特性和每次划分的对称性有关，如果每次都是划分在第一个位置，则算法复杂

T(n)=O(1),n=1;

T(n)=T(n-1)+O(n),n>1;

最好情况下，每次划分都很均匀

T(n)=O(1),n=1;

T(n)=2T(n/2)+O(n),n>1;

/*
	快速排序程序模块


	分治算法的案例
	以中心点a[p]找出在p，到r中间的比a[p]小的和比a[p]大的并交换成所需的顺序

*/

void swap(int a[],int i,int j)
{
	int temp;
	temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
int partition(int a[],int p,int r)
{
	int i=p;
	int j=r+1;
	int x=a[p];
	while(1)
	{
		while(a[++i]<=x);
		while(a[--j]>=x);

		if(i>=j){
			break;
		}
		swap(a,i,j);
	}
	a[p]=a[j];
	a[j]=x;

	return j;
}

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);
	}
}

 改进方法：基准元素由随机数生成下标

 

2.归并排序

    目标：将数组a[p:r]逐步对半分解，直到只剩下一个元素的时候它就是有序的数组，进而和另一个分解出来长度为1的数组进行合并，合并的时候排序，生成长度为2的有序数组，不断递归最后生成原问题的解：有序数组。

 

 

根据图解很容易就能明白。程序实现的过程中需要借助一个暂存数组b，在对a数组操作时候转到b数组的操作可以保证信息的不丢失，最后将排好的数组b复制到a的对应位置上，即可完成。

/*
	归并排序程序模块
	分成长度为1的数组，进而与另一个单元数组合并成2长度的数组并排序
*/

void merge(int a[],int b[],int low,int mid,int high)
{
	int s=low,t=mid+1,k=low;
	while(s<=mid && t<=high){
		if(a[s]<a[t]){
			b[k]=a[s];
			s++;
		
		}else{
			b[k]=a[t];
			t++;
		}
		k++;
	}
		if(s==mid+1){
			for(int i=k;i<=high;i++)b[i]=a[t++];
		}else{
			for(int i=k;i<=high;i++)b[i]=a[s++];
		}
		for(int i=low;i<=high;i++)a[i]=b[i];//复制回原数组
	
}
void mergeSort(int a[],int b[],int low,int high)
{
	if(low<high){
		int mid=(low+high)/2;
		mergeSort(a,b,low,mid);
		mergeSort(a,b,mid+1,high);
		merge(a,b,low,mid,high);
	}

}

 快速排序和归并排序是入门的时候比较难看懂的分治算法，比较起二分法的案例程序的结构更加抽象难懂，主要是递归之后结构变得复杂了。