1 传统的快速排序算法与分析
1.1 传统的快速排序算法 快速排序算法采用了分治技术，其分治步骤为：首
先，问题划分。将求解问题分成若干大小不等的子问 题；其次，递归求解。独立地解决这些子问题；最后，合 并解。将子问题的解归并成原问题的解。由于快速排 序可以采用就地重排，合并解不需要花费时间。因此影 响算法的最关键的问题是支点元素的选择方法是否适 当，是否可以将问题均等的划分。
Abstract：Quick sort is one of sorting algorithms with better performance，but it has choke point when sorted data is in ba⁃ sic sort order. In order to ensure high efficiency of quick sort in any case，based on a full analysis of the time efficiency of quick sorting algorithm，it is pointed out that the main factor which affects the efficiency of quick sorting algorithms is the selec⁃ tion of pointing element. Therefore，a quick sorting method of selecting the pointing element randomly is proposed，which makes the occurrence of the worst case well avoided. The correctness and efficiency of the improved algorithm were verified by experi⁃ ments.
文献标识码：A
文章编号：1004-373X（2013）20-0054-03
Analysis and research of quick sorting algorithm
WANG Chun-hong，WANG Wen-xia
（Department of Computer Science and technology，Yuncheng University，Yuncheng 044000，China）
∑ ( ) n-1
Cmax = (n - i) = n(n - 1) 2 = O n2
i=1
如果按上面给出的划分算法，当待排元素集 S 已按 递增有序（或递减有序）排列时，每次取当前待排数据的 第 1 个元素为支点，那么每次划分所取的支点就是当前 待排数据中关键字最小（或最大）的记录，则快速排序所 需的比较次数达到最多。即当元素基本有序时，快速排 序的效率反而很低，不及冒泡排序及插入排序。
QuickSor（t S，L，m-1） //对左区间递归快排 QuickSor（t S，m+1，H） //对右区间递归快排 }｝
对待排元素集 S 进行排序，最初的调用是 QuickSort （S，1，length[S]）。 而 快 速 排 序 算 法 的 关 键 是 PARTI⁃ TION 过程，它对子元素集 S [L..H]进行一趟快速排序或 一次划分：
传统的快速排序算法是从待排数据两端选取一个 元素作为支点元素，其递归快速排序算法 QuickSort 如 下：
QuickSor（t &S，L，H）｛ //对待排元素 S[L..H]进行快速排序
int m；//标识上次划分支点元的位置 if l<h //区间长度大于 1 时才须排序 { m ←PARTITION（S，L，H） //调用分治法找到 m 的值
Step5 重复执行 Step3，Step4，直到 i=j。并将 S[i]← pivot，返回 i 值。 1.2 传统快速排序算法的效率分析
算法的时间开销主要花费在划分 PARTITION 操作 上，对长度为 n 的数据元素进行一次划分，共需 n-1 次元 素的比较。
（1）最好情况时间复杂度 最好情况下，快速排序的每次划分所选取的支点元 素恰好都是当前待排数据的“中两个子表的长度大致相等，即对 半划分。在此情况下，可得知快速排序要做 lg n 趟划 分，时间复杂度为 C（n）=O（nlg n）。 （2）最坏情况时间复杂度 最坏情况下，快速排序的每次划分选取的支点元素 恰好都是当前待排数据中关键字最小（或最大）的元素， 每次划分的结果为：支点左边的子表为空（或右边的子 表为空），而另一个非空的子表中元素个数仅比划分前 的待排数据中元素个数少 1 个。 在此情况下，快速排 序就要做 n-1 次划分，而第 i 次划分开始时区间长度为 n-i+1，所需的比较次数为 n-（i 1≤i≤n-1），故总的比较 次数达到最大值：
55
本文在对传统快速排序算法的优点及缺点进行充 分分析的基础上，指出影响快速排序的关键因素，提出 一种随机化的高效排序方法。它对待排序的数据初态 没有任何要求，或者说可以让任何的数据初态在排 序 时 达 到 均 匀 分 布 ，从 而 使 任 何 输 入 数 据 达 到 O （nlog n）的时间复杂度。
（4）空间复杂度 快速排序算法是一个递归算法，因此，系统会自动 开辟一个栈来辅助算法的执行。最坏情况下，递归树的 高度为 O（n），所需附加栈的空间为线性量级 O（n）。一 般情况下，如图 2 所示其递归树的高度为 O（lg n），执行 算法所需附加栈的空间为对数量级 O（lg n）。
2 快速排序算法的改进
一次划分 PARTITION 的算法步骤为： Step1 首先定义两个变量 i 和 j，并初始化 i=L，j=H ； Step2 选取第一个待排元素 S[L]作为支点元素，并 将支点元赋值给 pivot，即执行 pivot =S[L]； Step3 从 j 位置开始由后向前比较（j-- ），找到第一 个小于 key（支点元素的关键字）的元素 S[j]，交换 S[i]与 S[j]；同时，i++。 Step4 从 i 位置开始由前向后比较（i++），找到第一 个大于 key（支点元素的关键字）的 S[i]，S[i]与 S[j]交换； 同时，j--。
2013 年 10 月 15 日 第 36 卷第 20 期
54
现代电子技术 Modern Electronics Technique
Oct. 2013 Vol.36 No.20
快速排序算法的分析与研究
王春红，王文霞
（运城学院 计算机科学与技术系，山西 运城 044000）
摘 要：快速排序是排序算法中性能较好的一种，但存在对数据基本有序的情形下的性能瓶颈问题。为了保证快速排
序在任何情况下的高效性，在对快速排序算法的时间效率进行充分的分析的基础上，指出支点元素的选取是影响快速排序
算法效率的主要因素。提出了一种随机选择支点元素的快速快排方法，很好地避免了最坏情况的发生。通过实验验证了改
进算法的正确性和高效性。
关键词：快速排序算法；支点元素；时间效率；随机化快速排序
中图分类号：TN911-34；TP301.6
（3）平均时间复杂度 尽管快速排序的最坏时间为 O（n2），但就平均性能 而言，它是基于关键字比较的内部排序算法中速度最快 的，快速排序亦因此而得名。它的平均时间复杂度为 O（nlg n）[4]。 在此选择同一量级的堆排序进行了比较测试。在 相同的环境下，基于 C++语言平台，分以不同规模（100， 1 000，10 000，100 000）的随机数作为测试数据集。在 程序中根据数据个数的不同产生的随机整型数组，然后 分别让不同的排序算法来进行从小到大的排序。这里 两种排序算法在相同的输入规模中原始无序数据都是 一样的，以此来保证实验的公正性。每个排序算法中加 入计数器来记录排序过程中的比较次数，同时利用计时 函数得出排序时间。 表 1 为输入数据规模分别为 100，1 000，10 000，
的依赖，相当于 S[l..h]中的元素是随机分布的。
影响快速排序算法效率的主要因素是支点元素的 选取。若所选择的支点元素应能够将数组 S 分成大小 几乎相等的部分，就能保证快速排序算法的高效性。
假设 S 由 n 个不同元素组成，最好的选择方法是选 择 S 中元素的中值作为支点元素。比如，初始元素的关 键字为：333，4，11，23，57，要应选择 23 中值作为支点元 素。尽管有些理论上好的算法可以找到待排元素的中 值，但由于开销过大使得快速排序无法在实际中得到实 用[7]。比如，先对待排序的数据进行统计、求平均来选取 出最佳的支点元素，以确保快速排序的每一次划分位置 都正好处于待排序序列的正中间。其算法的本质是选 取了最合适的支点，但选取合适的支点本身是一个很浪 费时间的操作，因此其方法只能在某些特定情况下提高排 序效率，而在另一些情况下反而效率低于基本快速排序。
为 n 的单支二叉树。因此，保证快速排序在任何情况下 高效性，近年来被国内学者从各种不同的角度进行了 改进与优化[1-6]。
图 1 一趟快速排序示意图
收稿日期：2013-08-08 基金项目：国家自然科学基金资助项目（11241005）
图 2 快速排序递归深度示意图
第 20 期
王春红，等：快速排序算法的分析与研究
56
现代电子技术
2013 年第 36 卷
100 000 时两个算法的排序时间对比。实验结果表明， 一般情况下，快速排序的效率的确比堆排序要高。
表 1 堆排序与快速排序时间比较
数据规模
100
1 000
10 000
堆排序
0.038
0.558
7.594
快速排序
0.018
0.232
2.901
ms 100 000 60.497 17.300
针对快速排序支点元素的选取，能够有效改进排序 的效率，而又不额外增加开销的主要有以下两种方法。