算法导论习题7-4—快排中堆栈深度的优化

//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 sortvoid 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);	}}//tail recursive QuickSort//the deapth of the heap due to the run of recursive Quick Sort is lgn//直觉上每次partition如果都能对半划分，则递归的堆栈深度为lgn//但是这种情况为理想状态，我们可以每次都挑出划分的子数组中较短的进行递归的QuickSort//剩下的另一半用循环来处理。void TRQuickSort(int a[],int p,int r){	int q;	while(p<r)	{		q=RandomizedPartition(a,p,r);		if((q-p)<(r-q))		{			TRQuickSort(a,p,q-1);			p=q+1;		}		else		{			TRQuickSort(a,q+1,r);			r=q-1;		}	}}int main(){	int arr[10]={5,2,3,6,1,7,6,9,5,10};	TRQuickSort(arr,0,9);	int i;	for(i=0;i<10;i++)	{		cout<<arr[i]<<" ";	}	cout<<endl;	return 0;}//Quick_sort//time complexity is nlgn//