快速排序算法研究和探究

1、快速排序算法研究和探究摘要：快速排序是排序算法中性能较好的一种, 但存在对数据基本有序的情形下的性能瓶颈问题。为了保证 快速排序在任何情况下的高效性，在对快速排序算法的时间 效率进行充分的分析的基础上，指出支点元素的选取是影响 快速排序算法效率的主要因素。提出了一种随机选择支点元素的快速快排方法，很好地避免了最坏情况的发生。通过实 验验证了改进算法的正确性和高效性。关键词:快速排序算法;支点元素;时间效率；随机化快速排序中图分类号：tn911?34； tp301.6文献标识码：a文章编号:10047373x (2013) 20?0054?03快速排序(quicksort)是一种基于比较、划分的

2、排序方法。它基本思想是：在待排元素集s中选择一个元素x作 为支点(pivot),通过一趟排序将要排序的数据分割成独立 的两个子序列sl和sr,其中左部分sl的所有元素都小于或 等于支点元素，而右部分sr的所有元素都大于或等于支点 元素(升序排序)，其状态如图1所示。然后按此方法对 这两部分数据分别再进行快速排序，以此达到整个待排元素 有序，整个排序过程可以递归进行，其递归的深度可用二叉 树表示，如图2所示。从算法的思想可以得出，快速排序算 法是利用分治技术的典型例子。通常，大家公认快速排序是 基于比较的排序方法中平均比较次数最少、速度最快的排序 算法，平均时间复杂度为0 (nlbn)。但是，若

3、支点元素选择 不当，在划分的两个子序列元素个数极度不平衡时，快速排 序有效率会急剧下降，最坏情况下快速排序将蜕变为冒泡排 序，其时间复杂度为0 (n2),算法的递归深度就变成一棵深 度为n的单支二叉树。因此，保证快速排序在任何情况下高 效性，近年来被国内学者从各种不同的角度进行了改进与优 化l?6o本文在对传统快速排序算法的优点及缺点进行充分分 析的基础上，指出影响快速排序的关键因素，提出一种随机 化的高效排序方法。它对待排序的数据初态没有任何要求， 或者说可以让任何的数据初态在排序时达到均匀分布，从而 使任何输入数据达到0 (nlog n)的时间复杂度。1传统的快速排序算法与分析1. 1传统

4、的快速排序算法快速排序算法采用了分治技术，其分治步骤为：首先， 问题划分。将求解问题分成若干大小不等的子问题；其次， 递归求解。独立地解决这些子问题；最后，合并解。将子问 题的解归并成原问题的解。由于快速排序可以采用就地重 排，合并解不需要花费时间。因此影响算法的最关键的问题 是支点元素的选择方法是否适当，是否可以将问题均等的划 分。传统的快速排序算法是从待排数据两端选取一个元素 作为支点元素，其递归快速排序算法quicksort如下：quicksort (&s, l, h) /对待排元素sl. h进行快速排序int m； /标识上次划分支点元的位置if 1(3)平均时间复杂度尽管快速

5、排序的最坏时间为052),但就平均性能而言, 它是基于关键字比较的内部排序算法中速度最快的，快速排 序亦因此而得名。它的平均时间复杂度为0 (nig n) 4o在此选择同一量级的堆排序进行了比较测试。在相同的 环境下，基于c+语言平台，分以不同规模(100, 1 000, 10 000, 100 000)的随机数作为测试数据集。在程序中根 据数据个数的不同产生的随机整型数组，然后分别让不同的 排序算法来进行从小到大的排序。这里两种排序算法在相同 的输入规模中原始无序数据都是一样的，以此来保证实验的 公正性。每个排序算法中加入计数器来记录排序过程中的比 较次数，同时利用计时函数得出排序时间。表1

6、为输入数据规模分别为100, 1 000, 10 000, 100 000 时两个算法的排序时间对比。实验结果表明，一般情况下， 快速排序的效率的确比堆排序要高。表1堆排序与快速排序时间比较ms(4) 空间复杂度快速排序算法是一个递归算法，因此，系统会自动开辟 一个栈来辅助算法的执行。最坏情况下，递归树的高度为0 (n),所需附加栈的空间为线性量级0 (n)o 一般情况下， 如图2所示其递归树的高度为0 (lg n),执行算法所需附 加栈的空间为对数量级0 (lg n)o2快速排序算法的改进影响快速排序算法效率的主要因素是支点元素的选取。 若所选择的支点元素应能够将数组s分成大小几乎相等的部

7、分，就能保证快速排序算法的高效性。假设s由n个不同元素组成，最好的选择方法是选择s 中元素的中值作为支点元素。比如，初始元素的关键字为： 333, 4, 11, 23, 57,要应选择23中值作为支点元素。尽 管有些理论上好的算法可以找到待排元素的中值，但由于开 销过大使得快速排序无法在实际中得到实用7。比如，先 对待排序的数据进行统计、求平均来选取出最佳的支点元 素，以确保快速排序的每一次划分位置都正好处于待排序序 列的正中间。其算法的本质是选取了最合适的支点，但选取 合适的支点本身是一个很浪费时间的操作，因此其方法只能 在某些特定情况下提高排序效率，而在另一些情况下反而效 率低于基本快速排

8、序。针对快速排序支点元素的选取，能够有效改进排序的效 率，而又不额外增加开销的主要有以下两种方法。第1种方法是“三者取中"的规则8?9。普遍使用的 方法：首先，比较待排数据中第一、中间和最后一个位置 上元素的关键字，取三者之中值为支点元素。其次，在划分 开始前将该支点元素和该区间的第1个元素进行交换，此后 的划分过程与1. 1所给的partition算法完全相同。实践表 明，采用三元素取中值的规则只需要几条if语句的判断即 可，在时间上、空间上不会增加额外的开销，但结果可以大 大改善快速排序在最坏情况下的性能。第2种方法就是本文 所提出的随机化快速排序。算法思路：每趟划分选取哪一位

9、置上的元素作为支点不是固定的，而是用随机数产生器 random ( 1, h) 随机选取位于1和h之间的随机数t (lwtwh),用st作为支点元素。这就打破了传统快速排 序对数据元素初始输入的依赖，相当于sl.h中的元素是 随机分布的。可以看出，随机化的快速排序与一般的快速排序算法差 别很小。选择1和h之间中任意一个元素作为支点。只需要 将选中的支点元素与第一个位置上的元素互换swap (st, s)，之后同样调用partition (s, 1, h)算法进行划分。 随机化之后，算法的时间空间开销没有增加，但性能却得到 了改善，尤其是对待排序元素基本有序的情况下，不可能导 致最坏情况的发生。

10、可以严格地证明划分的每一步以非常大 的概率导致均匀划分，与初始输入分布无关10。经实验对 比，在元素有序情况下，两种排序算法在规模分别为100, 200, 500时比较次数的统计情况对比，如表2所示。表2元素有序两种排序比较次数统计同时，算法的随机化不仅仅适用于快速排序，也适用于 其他需要数据随机分布的算法。3结语快速排序是一种经典的排序算法，实例验证了在数据分 布均匀的情况下，其排序的效率优于同量级nlbn的堆排序。 但在一些特殊情形，如待排序数据有序，其效率低于或者远 远低于nlbn数量级，甚至蜕变为n2数量级，相对地限制了 快速排序的广泛应用。因此，针对影响快速排序关键问题支 点元素的选

11、取，提出了一种随机选取支点元素的方法，改进 了快速排序对待排元素初态的敏感性，通过实验验证了该算 法的正确性和实用性。但是若输入数据中有很多的相同数 据，随机化的效果也将直接减弱。参考文献1汤亚玲，秦锋高效快速排序算法研究j.计算机 工程，2011 (6)： 77?79.2刘娜，佟冶浅析c语言快速排序算法的改进j. 计算机系统应用，2008 (1)： 113?115.3周建钦超快速排序j.计算机工程与应用，2006,42 (9)： 41?424 连顺金.快速排序的一种改进算法j.三明学院学 报，2009 (4)： 43?455 宋鸿修分割方式的多线程快速排序算法j.计算 机应用,2010 (9)： 237492378.6 廣清.改进的按位拆分快速排序算法j.计算机应 用，20