改进的快速排序算法

改进的快速排序算法 Improved Fas t Sorting Algorithm 1，22杨锋英 刘会超 Yang Fengying Liu Huichao (1.武汉大学软件工程国家重点实验室，湖北 武汉 430072; 2.黄淮学院计算机科学系，河南 驻马店 463000) (1.Wuhan University State Key Lab of Software Engineering，Hubei Wuhan 430072; 2.Huanghuai University Department of Computer Science，Henan Zhumadian 463000) 摘 要:本文通过分析快速排序算法中固有的不足之处，提出了改进的快速排序算法，并对算法的时间复杂度进行分 析， 通过编写程序上机实验，将原算法与改进的算法运行所需时间进行比较，证明了改进算法的有效性。 关键词,排序;算法;快速排序;插入排序;时间复杂度 中图分类号:TP301 文献标识码:A 文章编号:1671-4792-(2010)1-0012-03 Abstract:This paper analyzes the inherent shortcomings of the quick sort algorithm, puts forward a improved quick sort algorithm, and analysis the algorithm's time complexity, through the experiments, compared the time that the original algorithm and the improved algorithm required to run， proved the effectiveness of improved algorithm. Keywords:Sort; Algorithm; Fast Sorting Algorithm; Insert Sorting Algorithm;Time Complexity 都在一定范围内进行变化，但变化有一定的限度，并围绕该0 引言 快速排序算法不仅是计算机数据处理中经常被采用且 限度上下波动，因此，通常在一个数列中会有部分数据是有 行之有效的算法之一，而且在其它算法研究中也常常用来作 序或者一样的。对于一般数据库中的数据而言，小区域内相 为参考和比较的对象。其原因是快速排序算法的二分有效性 同数据的存在是一种必然现象。快速排序在经过多次分解 作为定理经过了严格的证明。即使这样，快速排序算法也有 后，形成多个小规模数据区，这是最有可能产生这种小规模 致命的缺点，对其缺点，文中提出了相应对策。 数据区域数据相同或者数据已经有序的情况，但快速排序在 1 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的提出 处理相同数据或者有序数据排序时，每一次划分都是基于 首先，快速排序算法是基于划分—递归求解—合并(也 “单枝”树的无效划分，从而充分显示“了慢”的一面 [2][5]就是 Divide-Conquer-Combine) 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 的算法之一。对于该方 ，这也 是快速排序算法固有的、致命的缺点。 法中的划分部分，主要是采用重排数列的形式实现的，即将 2 改进算法 数列中的数，随机地选取任一元素作为支点元素，将数列中 对于上面提出的双重循环掩盖算法的线性本质问题，解 其它小于等于支点的元素放于支点的右边，大于支点的元素 决的办法是:对一组数据，首先假设首元素为支点元素，记下 [7]置于支点的左边，然后将支点位置返回给主调程序。而对 支点元素后的元素位置为新的首元素位置，同时记下给定的 于划分的程序实现部分，大部分文献采用双重循环的形式实 尾元素位置，接下来采用 While 语句通过从新的首元素[1][4][6]现的，这样，完全掩盖问题的线性本质，使算法 “走 一趟”的方法，边“走”边判断，如果新的首元素“快”的 理念受到影响。 恰好小于等于 支点元素，则新的首位置向后“走一步”，其次，在对部分有序或者区域相同数据处理方面。从对 否则对尾元素进行 判断，如果尾元素正好大于支点元素，现实生活中员工工资、企业利润等实际数据观察可知，数据 则尾位置向前走一 步，如果这两个条件都不成立，则“” 交换这两个位置的元素， 然后首尾位置分别向后和向“前走一步”，重复 while， 直到 首位置在尾位置后面结束。最后将支点由假设位置调整到划 改 进 的 分位置。通过这样一个过程，最终形成三分序列的格局，即小 快 速 于等于支点部分、支点、大于支点部分。采用的单重循环改进 排 序 算 划分算法如图一所示。 法 ? 图二 改进后的算法 的概率均 元素的概率相等，即每个元素被选中作为支点元素 行 n 个语 为，则改进后快速排序算法的时间复杂度为执 进行插 ? 句一次的时间，设为 n，m 为划分的块数，k为每一 块 数据)。 图一 单重循环改进划分算法 入排序所需时间(注:此处每一块中必存在大量相同 那么，时间复杂度的计算如公式(1)所示。 本算法中主要是利用 if 语句替换第二个 while 语句， 仍采用两端向中间走的方式。当一端走不通时，改为另一端 (1) 继续向中间走，只有两端都走不通时，才进行交换。通过if 语句的替换，使得算法的线性本质一目了然。 对于快速排序在处理小批量相同数据排序的单“ 由式(1)分析可知，在一定区域内存在批量重复数据时，能够接近 枝”树 问题，可以采用与其它算法相结合的办法。在排序 改进算法的时间复杂度明显优于其它算法，最好时算法中，插 入排序在处理小批量数据排序上，时间复杂度O(n)。 接近于 n，因 此，改进的算法是将快速排序与插入排序结合4 实验结果 时间进 起来。 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 一是对快速排序和改进后的快速排序在排序改进的快速排序算法思想是:对于给定的 n(n>=10000) 行的比较。所对比的快速排序算法是采用文献[1]中算法。表个数据序列，先调用单重循不改进划分算法中划分策略进行 若干区域的划分，若某个区域数据个数小于等于 100 个时， 中的数据产生方式若为随机产生表示该数列是 由C++ 语言加以控 则停止划分，对该区域进行插入排序。在插入排序中，又采用 的 rand()函数产生，若为受限则表示该数据是人为在 P41. 设立标志的方法对已经有序或者是相同数据排序进行判断， 可以看 制而产生的区域性 50 个相同数据的数列。实验是若在一遍扫描过程中，没有一次数据交换发生，则表明该数 快速排 8G、512M 内存的机器上运行的，从多次的试验结果 列已经有序，排序结束。 出，若数据是小区域性分散相同，则算法明显优于原改进后的算法如图二所示。 序算法。 3 时间复杂度 速排序算 5 结束语 设存在 n 个元素的数据序列，每个元素被选中作为支点 多次不同区域相同数据的实验表明，改进的快 13 科技广场 2010.1 表一 快速排序算法改进前后的时间比较社,2002:263-292. [2]Thomas H.Cormen,Charles E.Leiserson,Clifford Stein.Introduction to Algorithms [M].The MIT Press， 2001:145-182. [3]官章全.标准 C++ 库大全[M].北京:电子工业出版社， 2002. [4]周建钦.超快速排序算法[J].计算机工程与应用. 2006,(29):41-86. [5]王红梅,应红霞,季绍红.递归函数时 间复杂度的分析 [J].东北师范大学学报(自然科学版),2001,(4):111-113. [6]肖奎,吴天吉.快速排序算法的改进[J].福建电脑, 法不仅具备原有算法在处理数据二分法的优越性，并且采用 单重循环来缩短二分处理内时间花费，展示出算法的线性本 2008,(8):98-113. [7]Anany Levitin.The Design & Analysis of Algo- 质，同时充分运用插入排序在处理小规模相同数据排序的优 rithms[M].TSINGHUA UNIVERSITY PRESS,2007,(11):129- 越性。因此，改进的快速排序算法是正确、有效的。 135. 参考文献 [1]严蔚民,吴伟民.数据结构[M].北京:清华大学出版 14 file:///D|/我的资料/Desktop/新建文本文 档.txt Appliance Error (configuration_error) Your request could not be processed because of a configuration error: "Could not connect to LDAP server." For assistance, contact your network support team. file:///D|/我的资料/Desktop/新建文本文档.txt2012-07-12 20:42:52