快速排序(Quicksort) gaunthan Posted on Aug 7 2016 ? Sorting ? ? Algorithm ? > **快速排序**（quick sort）是另一种基于[分治法](http://leanote.com/blog/post/58a7b354ab6441489f003b6f)的重要排序算法。 ## 思想 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：选择一个**基准数**（枢纽元），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都小于或等于基准数，另外一部分的所有数据都要大于或等于基准数，然后再按此方法对这两部分数据分别进行快速排序。 <!--more--> 将数组 S 排序的基本算法由下列四步组成： 1. 如果 S 中元素个数是 0 或 1，则返回 2. 取 S 中一元素 v，称之为**枢纽元**（pivot） 3. 将S - {v}分成两个不相交集合：S1中的元素都大于v，S2中的元素都小于v 4. 返回 { quickSort(S1)，v，quickSort(S2) } ## 示意 你可以通过查看下面的动态图来获得直观的感受：  ## 枢纽元的选取 ### 错误的做法 通常的、没有经过充分考虑的选择是将第一个元素或最后一个元素用作枢纽元。如果输入是随机的，那么这是可以接受的。但是如果输入是预排序的或是反序的，那么这样的枢纽元就产生一个劣质的分割，因为所有的元素不是都被划入了 S1 就是被划入了 S2。实际上，如果第一个元素用作枢纽元而且输入是预先排序的，那么快速排序花费的时间将是二次的。 ```c pivot = A[right]; ``` ### 安全的做法 一种安全的做法是随机选取枢纽元。一般来说这种策略非常安全，因为随机的枢纽元不可能总在接连不断地产生劣质的分割。然而，随机数的生成一般代价昂贵，或许根本减少不了算法其余部分的平均运行时间。 ```c pos = Random(left, right); swap A[right] with A[pos] pivot = A[right]; ``` ### 三数中值法（Median-of-Three） 一组n个数的中值是第$\lceil n/2 \rceil$个最大的数。枢纽元的最好的选择是数组的中值。一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。下述函数将枢纽元放置于最右边第二个位置。由于最左边的元素小于或等于枢纽元、最右边的元素大于或等于枢纽元，使得双向分割时$i$和$j$不会越界。 ```cpp // 使用三数中值法获取枢纽元。该步骤过后，成立a[left] <= pivot <= a[right]， // 同时有a[right-1] == pivot ElementType Median3(ElementType a[], int left, int right) { int center = (left + right) / 2; // sort a[left], a[center] and a[right] if (a[left] > a[center]) Swap(&a[left], &a[center]); if (a[left] > a[right]) Swap(&a[left], &a[right]); if (a[center] > a[right]) Swap(&a[center], &a[right]); Swap(&a[center], &a[right - 1]); // hide pivot return a[right - 1]; // return pivot } ``` ## 分割策略 在分割阶段要做的就是把所有小于或等与枢纽元的元素移到数组的左边、把所有大于或等与枢纽元的元素移到数组的右边。调用该算法前应该使用好的策略选取枢纽元，并将其与最右边的元素交换（单向分割）或倒数第二个元素交换（双向分割），使其离开要被分割的区域： $A[left..right-1]$或$A[left..right-2]$。 ### 单路分割 从一端进行扫描的分割方案称为**Lomuto划分**： ```C LomutoPartition(A, left, right) pivot = A[right] small = left - 1 for i = left to right - 1 if(A[i] <= pivot) ++small // if small != i exchange A[small] with A[i] ++small exchange A[small] with A[right] return small ``` ### 双路分割 从两端进行扫描的分割方案称为**Hoare划分**： ```C HoarePartition(A, left, right) // 使用三数中值法获取枢纽元。该步骤过后，成立a[left] <= pivot <= a[right]， // 同时有a[right-1] == pivot pivot = Median3(a, left, right); i = left; j = right - 1; // 不将j置为right-2，以防止越界 while(true) { while (a[++i] < pivot) {} // a[right] >= pivot，因此不需要检测下标是否越界 while (a[--j] > pivot) {} // a[left] <= pivot，因此不需要检测下标是否越界 if (i >= j) break; Swap(&a[i], &a[j]); } Swap(&a[i], &a[right - 1]); // 把枢纽元的位置恢复为两个集合的中间 return i; ``` ## 实现 算法中的CUTOFF用于分辨排序的规模，因为当排序规模过小时宜采用直接插入排序： ```cpp #define CUTOFF 7 void QuickSort(ElementType a[], int left, int right) { int s; if (left + CUTOFF <= right) { s = HoarePartition(a, left, right); QuickSort(a, left, s - 1); QuickSort(a, s + 1, right); }else { InsertionSort(a + left, right - left + 1); } } ``` ## 效率 ### 最优情况 在最优的情况下，所有的分裂点都位于相应子数组的中点。这这种情况下，键值比较次数$C_{best}(n)$满足下列递推式： $$ 当n>1时，C_{best}(n) = 2C_{best}(n/2) + n, C_{best}(1) = 0$$ 根据[分治算法主定理](http://leanote.com/blog/post/58a7b354ab6441489f003b6f)，$C_{best}(n) \in \theta(nlog_2n)$；对于$n=2^k$的情况求得$C_{best}(n) = nlog_2n$。 ### 最差情况 在最差的情况下，所有的分裂点都趋于极端：两个子数组有一个为空，而另一个子数组仅仅比被划分的数组少一个元素。具体来说，当输入数组是有序的、而又只是简单地选择最左端或最右端的元素作为枢纽元时便会发生这种情况。如前文所言，在这种情况下，键值比较的总次数等于$\theta(n^2)$。 ### 平均情况 快速排序的平均情况分析比较复杂，有兴趣可以去查阅相关推导过程。总的来说，快速排序在平均情况下，仅比最优情况多执行39%的比较操作。此外，它的最内层循环效率非常高，使得在处理随机排列的数组时，速度要比归并排序快（对于堆排序也是如此）。 但是与其他排序算法一样，快速排序算法也有缺点： - 快速排序是不稳定的。 - 快速排序需要一个堆栈来存储那些还没有被排序到的子数组的参数（无论是递归还是迭代实现）。尽管可以通过总是先对较短子数组排序的方法来使堆栈的大小降低到$O(logn)$，但是它还是比堆排序$O(1)$的空间效率差。 - 虽然有很多巧妙的选择枢纽元的方法，使得最差情况下时间效率为$\theta(n^2)$的可能性较小，但是这种可能性还是存在的。 - 即使是对于随机数组的排序，排序性能的好坏，不仅与算法的具体实现有关，还与计算机的系统结构和数据类型有关。 ## References - ThomasH.Cormen. 算法导论[M]. 机械工业出版社, 2013. - MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010. - 莱维汀, A.). 算法设计与分析基础(第3版)[M]. 清华大学出版社, 2015. 赏 Wechat Pay Alipay 冒泡排序(Bubble sort) 归并排序(Merge sort)
