博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
对于快速排序算法的递归栈深度的一点改进
阅读量:6713 次
发布时间:2019-06-25

本文共 2420 字,大约阅读时间需要 8 分钟。

  前几天有人问了我一个关于快速排序的问题。起因是严蔚敏版数据结构第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 #include 
10 #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<<"函数调用总次数:"<
<

  另外今天是万圣节。

转载于:https://www.cnblogs.com/allen8807/archive/2012/11/01/2749551.html

你可能感兴趣的文章
kindeditor粘贴word文档内容时去除格式的方法?如何设置为默认无文本格式呢?
查看>>
IT 名企招聘信息
查看>>
this web application instance has been stopped already解决办法
查看>>
【计导作业】链表——成绩统计2
查看>>
Xen安全架构sHype/ACM策略配置图文教程
查看>>
汇编语言--百度百科
查看>>
OpenGL学习之路(三)
查看>>
sql ltrim rtrim
查看>>
几点基于Web日志的Webshell检测思路
查看>>
mysql sql_mode 之 NO_ENGINE_SUBSTITUTION
查看>>
嵌入式系统 Boot Loader 技术内幕【转】
查看>>
(windows)一台电脑上安装两个Mysql服务
查看>>
教你如何在Kali Linux 环境下设置蜜罐?
查看>>
微信公众号开发之公众号支付
查看>>
主域控角色迁移和夺取(转载)
查看>>
HDFS High Availability Using the Quorum Journal Manager
查看>>
Sql日期时间格式转换
查看>>
mesos+marathon+zookeeper的docker管理集群亲手搭建实例(环境Centos6.8)
查看>>
你应了解的4种JS设计模式
查看>>
垃圾收集器Serial 、Parallel、CMS、G1
查看>>