算法导论第七章例题——快速排序

快速排序的平均意义上的时间复杂度是nlgn，最差意义上的时间复杂度是n*n，算法的好坏取决于所选取的用于划分数组的元素的大小。

算法的思路是：将数组按照某个元素划分为两个部分，并单独对这两个部分数组进行就地排序，就地排序时重复利用划分的方法将数组分为更小的两部分。

本代码中为了使代码具有平均意义上的时间复杂度，添加了RandomizedPartition函数进行优化，该函数的思路是随机选取介于p和r之间的元素和

r元素互换，然后再按照a[r]进行划分数组。

//Quick_sort
//time complexity is nlgn
//the way is find an element,and partition the array according to this element

#include<iostream>
using namespace std;
int Partition(int a[],int p,int r)
{
	int num=a[r];
	int i=p-1;
	int j,temp;
	//partition the array according to num
	for(j=p;j<=r-1;j++)
	{
		if(a[j]<num)
		{
			i+=1;
			temp=a[j];
			a[j]=a[i];
			a[i]=temp;
		}
	}
	//Insert the num between the partion
	temp=a[r];
	a[r]=a[i+1];
	a[i+1]=temp;
	//return the partition boundray
	return i+1;
}
//Randomized Partition,in this function we random select
//the element in array,and exchange it with the lase element in array
//the target is lowdown the average time complexity !
int RandomizedPartition(int a[],int p,int r)
{
	//generate i between  p and r
	int i=rand()%(r+1-p)+p;
	int temp;
	temp=a[i];
	a[i]=a[r];
	a[r]=temp;
	return Partition(a,p,r);
}
//recursive calls QuickSort to cpmplate the sort
void QuickSort(int a[],int p,int r)
{
	int q;
	if(p<r)
	{
		q=RandomizedPartition(a,p,r);
		QuickSort(a,p,q-1);
		QuickSort(a,q+1,r);
	}
}

int main()
{
	int arr[10]={5,2,3,6,1,7,6,9,5,10};
	QuickSort(arr,0,9);
	int i;
	for(i=0;i<10;i++)
	{
		cout<<arr[i]<<" ";
	}
	cout<<endl;
	return 0;
}