8.3.2　快速排序

1.快速排序的基本思想

快速排序（quick sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

对待排序记录序列进行一趟快速排序的过程描述如下。

（1）初始化：取第一个记录作为基准，其关键字值为19，设置两个指针i、j分别用来指示将要与基准记录进行比较的左侧记录位置和右侧记录位置。最开始从右侧开始比较，当发生交换操作后，转去再从左侧比较。

（2）用基准记录与右侧记录进行比较，即与指针j指向的记录进行比较，如果右侧记录的关键字值大，则继续与右侧前一个记录进行比较，即j减1后，再用基准元素与j指向的记录比较，若右侧的记录小（逆序），则将基准记录与j指向的记录进行交换。

（3）用基准元素与左侧记录进行比较，即与指针i指向的记录进行比较，如果左侧记录的关键字值小，则继续与左侧后一个记录进行比较，即i加1后，再用基准记录与i指向的记录比较，若左侧的记录大（逆序），则将基准记录与i指向的记录交换。

（4）右侧比较与左侧比较交替重复进行，直到指针i与j指向同一位置，即指向基准记录最终的位置。

一趟快速排序之后，再分别对左右两个区域进行快速排序，依此类推，直到每个分区域都只有一个记录为止。

2.快速排序算法

快速排序是一个递归的过程，只要能够实现一趟快速排序的算法，就可以利用递归的方法对一趟快速排序后的左右分区域分别进行快速排序。下面是一趟快速排序的算法分析。

（1）初始化：

将i和j分别指向待排序区域的最左侧记录和最右侧记录的位置。

将基准记录暂存在temp中。

（2）对当前待排序区域从右侧将要进行比较的记录（j指向的记录）开始向左侧进行扫描，直到找到第一个关键字值小于基准记录关键字值的记录：

（3）如果i！＝j，则将a［j］中的记录移至a［i］，并将i＋＋：

（4）对当前待排序区域从左侧将要进行比较的记录（i指向的记录）开始向右侧进行扫描，直到找到第一个关键字值大于基准记录关键字的记录：

（5）如果i！＝j，则将a［i］中的记录移至a［j］，并将j＋＋：

（6）如果此时仍有i＜j，则重复上述（2）～（5）操作，否则，表明找到了基准记录的最终位置，并将基准记录移到它的最终位置上：

排序过程如图8－8所示，下面是快速排序的完整算法。

算法8.6 快速排序算法

整个快速排序的过程可递归进行，若待排序列中只有一个记录，显然已有序，否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序，如图8－9所示。

图8－8 快速排序一趟快排过程

图8－9 快速排序全过程

从图示可看出，快速排序分为两个部分来完成，第一部分，分块，即将关键字按中轴元素分为两部分，一部分都比中轴元素小，另一部分都比中轴元素大。第二部分排序，分块后，块内排序，将上个算法拆分后如下。

快速排序函数如下：

第1个被调函数是排序函数，分块之后内部排序，这个函数是递归函数，算法如下。

算法8.7 快速排序块内排序

第1个函数中调用分块函数，这是快速排序中最重要的函数，算法如下。

算法8.8 快速排序分块函数

3.快速排序的时间复杂度

快速排序的平均时间为Tavg（n）＝knlog2n，其中n为待排序序列中记录的个数，k为某个常数，经验证明，在所有同数量级的此类（先进的）排序方法中，快速排序的常数因子k最小。因此，就平均时间而言，快速排序目前被认为是最好的一种内部排序方法。

下面我们来分析快速排序的平均时间性能。

假设T（n）为对n个记录L.r［1..n］进行快速排序所需时间，则由算法QuickSort可见，T（n）＝Tpass（n）＋T（k－1）＋T（n－k），其中Tpass（n）为对n个记录进行一趟快速排序Partition（L，1，n）所需时间，从算法8.8可见，它和记录数n成正比，可以用cn表示之（c为某个常数）；T（k－1）和T（n－k）分别为对L.r［1..k－1］和L.r［k＋1..n］中记录进行快速排序QSort（L，1，k－1）和QSort（L，k＋1，n）所需时间。假设待排序列中的记录是随机排列的，则在一趟排序之后，k取1至n之间任何一值的概率相同，快速排序所需时间的平均值则为

假定Tavg（1）≤b（b为某个常量），由上式可推出

通常，快速排序被认为是，在所有同数量级（O（nlog2n））的排序方法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，其时间复杂度为O（n）。为改进之，通常依“三者取中”的法则来选取枢轴记录，即比较L.r［s］.key、L.r［t］.key和，取三者中其关键字取中值的记录为枢轴，只要将该记录和L.r［s］互换，算法8.8不变。经验证明，采用三者取中的规则可大大改善快速排序在最坏情况下的性能。然而，即使如此，也不能使快速排序在待排记录序列已按关键字有序的情况下达到O（n）的时间复杂度。为此，可如下所述修改“一次划分”算法：在指针high减1和low增1的同时进行“冒泡”操作，即在相邻两个记录处于“逆序”时进行互换，同时在算法中附设两个布尔型变量分别指示指针low和high在从两端向中间的移动过程中是否进行过交换记录的操作，若指针low在从低端向中间的移动过程中没有进行交换记录的操作，则不再需要对低端子表进行排序；类似地，若指针high在从高端向中间的移动过程中没有进行交换记录的操作，则不再需要对高端子表进行排序。显然，如此“划分”将进一步改善快速排序的平均性能。

由以上讨论可知，从时间上看，快速排序的平均性能优于前面讨论过的各种排序方法，从空间上看，前面讨论的各种方法，都只需要一个记录的附加空间即可，但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为（包括最外层参量进栈），但是，若每趟排序之后，枢轴位置均偏向子序列的一端，则为最坏情况，栈的最大深度为n。如果改写算法8.8，在一趟排序之后比较分割所得两部分的长度，且先对长度短的子序列中的记录进行快速排序，则栈的最大深度可降为O（log2n）。

因为每趟确定的元素呈指数增加，因此快速排序的时间效率为O（nlog2n）；又因为递归要用栈（存每层low、high和pivot），其空间效率为O（log2n）；而因为快速排序有跳跃式交换，所以属于不稳定排序。但是因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以排序特别快。

4.快速排序对最差情况的改进

为防止最差情况的出现，一般采取“三者取中”法来确定枢轴。即在第一个记录和最后一个记录，以及中间位置的记录中，选取值为中间的那个来作枢轴，这样就能防止最差情况的出现。

快速排序实质上是对冒泡排序的一种改进，它的效率与冒泡排序相比有很大的提高。在冒泡排序过程中是对相邻两个记录进行关键字比较和互换的，这样每次交换记录后，只能改变一对逆序记录，而快速排序则从待排序记录的两端开始进行比较和交换，并逐渐向中间靠拢，每经过一次交换，有可能改变几对逆序记录，从而加快了排序速度。到目前为止快速排序是平均速度最大的一种排序方法，但当原始记录排列基本有序或基本逆序时，每一趟的基准记录有可能只将其余记录分成一部分，这样就降低了时间效率，所以快速排序适用于原始记录排列杂乱无章的情况。

快速排序是一种不稳定的排序，在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息。