长安大学 快速排序 数据结构
一、 摘要
1962 年，伦敦 Elliot ltd 公司的 Tony Hoare 发明了快速排序（QuickSort）方法。
它几乎是最快的排序方法，并被评为 20 世纪十大算法之一。它基于分治法，即将问题分
为若干子问题，再对每个子问题求解，最后将所有子问题的解合成一个综合的解，得到原
始问题的解。快速排序适用于较长数组的排序，用途极为广泛。另外，它还有若干优化形
式，在此仅对最基本的快速排序作讨论。
二、 关键字
快速排序（QuickSort） 轴值（pivot） 分割（paron） 时间复杂度 空间复杂度
三、 算法思想
1、 从待排序序列 S 中任意选择一个记录 k 作为轴值（pivot）。
2、 将剩余的记录分割（paron）成左子序列 L 和右子序列 R。
3、 L 中的所有记录都小于或等于 k，R 中的记录都大于或等于 k，因此 k 刚好位于正确的位
置。
4、 对子序列 L 和 R 递归进行快速排序，直到序列中只含 0 或 1 个元素，退出递归。
四、 算法实现
1、 流程图
是
否
图 1 快速排序流程图
准备
输入数组长度
n 和数组 a[]
序列中元
素<=1
若大于 pivot，则放入
右子序列 r；否则放入
左子序列 l。
输出排序
结果
选择轴值
（pivot）
是否大于
pivot
停止
