前几天有人问了我一个关于快速排序的问题。起因是严蔚敏版数据结构第277页的一句话:“如果改写算法10.7,在一趟排序之后比较分割所得两部分的长度,且先对长度短的子序列中的记录进行快速排序,则栈的最大深度可降为O(logn)。”(注:这里的logn是log2n的简写)。
因为对于原地排序而言,额外的空间复杂度应该是常数,但由于快速排序的实现一般是递归的方式,所以快速排序的额外空间复杂度不是常数,而是和递归深度相关。
回到一开始的问题上来,刚看到那句话还觉得奇怪,因为话里的栈的深度是指函数递归调用的深度,这个和处理两个子序列的顺序应该是无关的,除非还在递归方面有其它改进,例如回溯到上上级。顺着这个思路来想,觉得改进栈的最大深度是有可能的。
这个改进的主要思想应该是:用没处理的子节点代替父节点,以减少栈的深度。
假设父节点A,子节点B、C。处理完B后,并不直接处理C而是回溯回A,并把C交到A这一级来处理。通过这种方法的确可以将栈的最大深度降到O(logn)。详细的数学证明就不写了。
下面是具体的实现代码。代码里把两种快速排序都列出来了,以方便对比。实验结果也证实是在递归深度是在logn以内。
1 /*** 2 *对于快速排序递归函数栈的深度的改进 3 *author:Allen 4 *date:2012-11-01 5 *说明: 6 *由于只是简单实现算法,对于代码风格没太在意。 7 *原快速排序算法的代码是从网上找的,并做了一点修改。 8 */ 9 #include10 #include 11 using namespace std; 12 const int a_size = 128;//带排序数列长度 13 int a[a_size]; 14 void swap(int *pLeft,int *pRight) 15 { 16 int temp; 17 temp = *pLeft; 18 *pLeft= *pRight; 19 *pRight = temp; 20 } 21 //原快速排序 22 void qs(int begin,int end) 23 { 24 static int deep = 0;//递归深度 25 static int allnum =0;//函数调用总次数 26 static int mostDeep = 0;//最大递归深度 27 ++allnum; 28 ++deep; 29 if(deep>mostDeep){ 30 mostDeep=deep; 31 } 32 int compare=a[begin], left =begin,right = end; 33 if(abs(right-left)<=1) 34 { 35 --deep; 36 if(left a[right]){ 37 swap(a[right],a[left]); 38 } 39 return; 40 } 41 while (left =compare) 44 right--; 45 swap(a[left],a[right]); 46 while ((left mostDeep){ 73 mostDeep=deep; 74 } 75 // cout<<"递归深度:"< << ' ' < <<' ' < <<' ' < <<' ' < <<' ' < a[right]){ 81 swap(a[right],a[left]); 82 } 83 p_unBegin=-1; 84 p_unEnd=-1; 85 return; 86 } 87 while (left =compare) 90 --right; 91 92 swap(a[left],a[right]); 93 while ((left 1){115 --deep;116 return;117 }118 }else{119 p_unBegin=p_begin;120 p_unEnd=right-1;121 newBegin=right+1;122 newEnd=p_end;123 qs(newBegin,newEnd,unBegin,unEnd);124 while(unBegin!=-1&&unEnd!=-1){125 qs(unBegin,unEnd,unBegin,unEnd);126 } 127 if(deep>1){128 --deep;129 return;130 }131 } 132 //另一部分133 qs(p_unBegin,p_unEnd,unBegin,unEnd);134 while(unBegin!=-1&&unEnd!=-1){135 qs(unBegin,unEnd,unBegin,unEnd);136 }137 --deep;138 if(deep<=0){139 cout<<"函数调用总次数:"< <
另外今天是万圣节。