算法导论习题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 numfor(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 partiontemp=a[r];a[r]=a[i+1];a[i+1]=temp;//return the partition boundrayreturn 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 rint 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;}
优化的尾递归使得快速排序的堆栈深度为lgn。
