资源描述：
《快速排序算法研究和探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、快速排序算法研究和探究摘要：快速排序是排序算法中性能较好的一种,但存在对数据基本有序的情形下的性能瓶颈问题。为了保证快速排序在任何情况下的高效性，在对快速排序算法的时间效率进行充分的分析的基础上，指出支点元素的选取是影响快速排序算法效率的主要因素。提出了一种随机选择支点元素的快速快排方法，很好地避免了最坏情况的发生。通过实验验证了改进算法的正确性和高效性。关键词:快速排序算法;支点元素;时间效率；随机化快速排序中图分类号：TN911?34；TP301.6文献标识码：A文章编号:10047373X
2、(2013)20?0054?03快速排序(Quicksort)是一种基于比较、划分的排序方法。它基本思想是：在待排元素集S中选择一个元素x作为支点(Pivot),通过一趟排序将要排序的数据分割成独立的两个子序列SL和SR,其中左部分SL的所有元素都小于或等于支点元素，而右部分SR的所有元素都大于或等于支点元素(升序排序)，其状态如图1所示。然后按此方法对这两部分数据分别再进行快速排序，以此达到整个待排元素有序，整个排序过程可以递归进行，其递归的深度可用二叉树表示，如图2所示。从算法的思想可以得出
3、，快速排序算法是利用分治技术的典型例子。通常，大家公认快速排序是基于比较的排序方法中平均比较次数最少、速度最快的排序算法，平均时间复杂度为0(nlbn)。但是，若支点元素选择不当，在划分的两个子序列元素个数极度不平衡时，快速排序有效率会急剧下降，最坏情况下快速排序将蜕变为冒泡排序，其时间复杂度为0(n2),算法的递归深度就变成一棵深度为n的单支二叉树。因此，保证快速排序在任何情况下高效性，近年来被国内学者从各种不同的角度进行了改进与优化[l?6]o本文在对传统快速排序算法的优点及缺点进行充分分析
4、的基础上，指出影响快速排序的关键因素，提出一种随机化的高效排序方法。它对待排序的数据初态没有任何要求，或者说可以让任何的数据初态在排序时达到均匀分布，从而使任何输入数据达到0(nlogn)的时间复杂度。1传统的快速排序算法与分析1.1传统的快速排序算法快速排序算法采用了分治技术，其分治步骤为：首先，问题划分。将求解问题分成若干大小不等的子问题；其次，递归求解。独立地解决这些子问题；最后，合并解。将子问题的解归并成原问题的解。由于快速排序可以采用就地重排，合并解不需要花费时间。因此影响算法的最关键
5、的问题是支点元素的选择方法是否适当，是否可以将问题均等的划分。传统的快速排序算法是从待排数据两端选取一个元素作为支点元素，其递归快速排序算法Quicksort如下：QuickSort(&S,L,H){//对待排元素S[L..H]进行快速排序intm；//标识上次划分支点元的位置if1(3)平均时间复杂度尽管快速排序的最坏时间为052),但就平均性能而言,它是基于关键字比较的内部排序算法中速度最快的，快速排序亦因此而得名。它的平均时间复杂度为0(nign)[4]o在此选择同一量级的堆排序进行了比较
6、测试。在相同的环境下，基于C++语言平台，分以不同规模(100,1000,10000,100000)的随机数作为测试数据集。在程序中根据数据个数的不同产生的随机整型数组，然后分别让不同的排序算法来进行从小到大的排序。这里两种排序算法在相同的输入规模中原始无序数据都是一样的，以此来保证实验的公正性。每个排序算法中加入计数器来记录排序过程中的比较次数，同时利用计时函数得出排序时间。表1为输入数据规模分别为100,1000,10000,100000时两个算法的排序时间对比。实验结果表明，一般情况下，快
7、速排序的效率的确比堆排序要高。表1堆排序与快速排序时间比较ms(4)空间复杂度快速排序算法是一个递归算法，因此，系统会自动开辟一个栈来辅助算法的执行。最坏情况下，递归树的高度为0(n),所需附加栈的空间为线性量级0(n)o一般情况下，如图2所示其递归树的高度为0(lgn),执行算法所需附加栈的空间为对数量级0(lgn)o2快速排序算法的改进影响快速排序算法效率的主要因素是支点元素的选取。若所选择的支点元素应能够将数组S分成大小几乎相等的部分，就能保证快速排序算法的高效性。假设S由n个不同元素组成
8、，最好的选择方法是选择S中元素的中值作为支点元素。比如，初始元素的关键字为：333,4,11,23,57,要应选择23中值作为支点元素。尽管有些理论上好的算法可以找到待排元素的中值，但由于开销过大使得快速排序无法在实际中得到实用［7］。比如，先对待排序的数据进行统计、求平均来选取出最佳的支点元素，以确保快速排序的每一次划分位置都正好处于待排序序列的正中间。其算法的本质是选取了最合适的支点，但选取合适的支点本身是一个很浪费时间的操作，因此其方法只能在某些特定情况下提高排序效率，而在另一些情况下反而
