上篇文章介绍了时间复杂度为O(nlgn)的合并排序，本篇文章介绍时间复杂度同样为O(nlgn)但是排序速度比合并排序更快的快速排序(Quick Sort)。
快速排序是20世纪科技领域的十大算法之一 ，他由C. A. R. Hoare于1960年提出的一种划分交换排序。
快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中，对数组，列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序在面试中经常会遇到。
本文首先介绍快速排序的思路，算法的实现、分析、优化及改进，最后分析了.NET 中列表排序的内部实现。
一 原理
快速排序的基本思想如下：
- 对数组进行随机化。
- 从数列中取出一个数作为中轴数(pivot)。
- 将比这个数大的数放到它的右边，小于或等于它的数放到它的左边。
- 再对左右区间重复第三步，直到各区间只有一个数。
如上图所示快速排序的一个重要步骤是对序列进行以中轴数进行划分，左边都小于这个中轴数，右边都大于该中轴数，然后对左右的子序列继续这一步骤直到子序列长度为1。
下面来看某一次划分的步骤，如下图：
上图中的划分操作可以分为以下5个步骤：
- 获取中轴元素
- i从左至右扫描，如果小于基准元素，则i自增，否则记下a[i]
- j从右至左扫描，如果大于基准元素，则i自减，否则记下a[j]
- 交换a[i]和a[j]
- 重复这一步骤直至i和j交错，然后和基准元素比较，然后交换。
划分过程的代码实现如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
/// <summary> /// 快速排序中的划分过程 /// </summary> /// <param name="array">待划分的数组</param> /// <param name="lo">最左侧位置</param> /// <param name="hi">最右侧位置</param> /// <returns>中间元素位置</returns> private static int Partition(T[] array, int lo, int hi) { int i = lo, j = hi + 1; while (true) { //从左至右扫描，如果碰到比基准元素array[lo]小，则该元素已经位于正确的分区，i自增，继续比较i+1； //否则，退出循环，准备交换 while (array[++i].CompareTo(array[lo]) < 0) { //如果扫描到了最右端，退出循环 if (i == hi) break; } //从右自左扫描，如果碰到比基准元素array[lo]大，则该元素已经位于正确的分区，j自减，继续比较j-1 //否则，退出循环，准备交换 while (array[--j].CompareTo(array[lo]) > 0) { //如果扫描到了最左端，退出循环 if (j == lo) break; } //如果相遇，退出循环 if (i >= j) break; //交换左a[i],a[j]右两个元素，交换完后他们都位于正确的分区 Swap(array, i, j); } //经过相遇后，最后一次a[i]和a[j]的交换 //a[j]比a[lo]小，a[i]比a[lo]大，所以将基准元素与a[j]交换 Swap(array, lo, j); //返回扫描相遇的位置点 return j; } |
划分前后，元素在序列中的分布如下图：
二 实现
与合并算法基于合并这一过程一样，快速排序基于分割(Partition)这一过程。只需要递归调用Partition这一操作，每一次以Partition返回的元素位置来划分为左右两个子序列，然后继续这一过程直到子序列长度为1，代码的实现如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class QuickSort<T> where T : IComparable<T> { public static void Sort(T[] array) { Sort(array, 0, array.Length - 1); } private static void Sort(T[] array, int lo, int hi) { //如果子序列为1，则直接返回 if (lo >= hi) return; //划分，划分完成之后，分为左右序列，左边所有元素小于array[index]，右边所有元素大于array[index] int index = Partition(array, lo, hi); //对左右子序列进行排序完成之后，整个序列就有序了 //对左边序列进行递归排序 Sort(array, lo, index - 1); //对右边序列进行递归排序 Sort(array, index + 1, hi); } } |
下图说明了快速排序中，每一次划分之后的结果：
一般快速排序的动画如下：
三 分析
- 在最好的情况下，快速排序只需要大约nlgn次比较操作，在最坏的情况下需要大约1/2 n2 次比较操作。在最好的情况下，每次的划分都会恰好从中间将序列划分开来，那么只需要lgn次划分即可划分完成，是一个标准的分治算法Cn=2Cn/2+N，每一次划分都需要比较N次，大家可以回想下我们是如何证明合并排序的时间复杂度的。
在最坏的情况下，即序列已经排好序的情况下，每次划分都恰好把数组划分成了0，n两部分，那么需要n次划分，但是比较的次数则变成了n, n-1, n-2,….1, 所以整个比较次数约为n(n-1)/2~n2/2.
- 快速排序平均需要大约2NlnN次比较，来对长度为n的排序关键字唯一的序列进行排序。 证明也比较简单：假设CN为快速排序平均花在比较上的时间，初始C0=C1=0，对于N>1的情况，有：
其中N+1是分割时的比较次数，
表示将序列分割为0，和N-1左右两部分的概率为1/N, 划分为1，N-2左右两部分的概率也为1/N，都是等概率的。然后对上式左右两边同时乘以N，整理得到：
然后，对于N为N-1的情况：
两式相减，然后整理得到：
然后左右两边同时除以N(N+1)，得到:
可以看到，这是一个递归式，我们将
递归展开得到：
然后处理一下得到：
- 平均情况下，快速排序需要大约1.39NlgN次比较，这比合并排序多了39%的比较，但是由于涉及了较少的数据交换和移动操作，他要比合并排序更快。
- 为了避免出现最坏的情况，导致序列划分不均，我们可以首先对序列进行随机化排列然后再进行排序就可以避免这一情况的出现。
- 快速排序是一种就地(in-place)排序算法。在分割操作中只需要常数个额外的空间。在递归中，也只需要对数个额外空间。
- 另外，快速排序是非稳定性排序。
快速排序是20世纪科技领域的十大算法之一 ，他由C. A. R. Hoare于1960年提出的一种划分交换排序。
快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中，对数组，列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序在面试中经常会遇到。
本文首先介绍快速排序的思路，算法的实现、分析、优化及改进，最后分析了.NET 中列表排序的内部实现。
一 原理
快速排序的基本思想如下：
- 对数组进行随机化。
- 从数列中取出一个数作为中轴数(pivot)。
- 将比这个数大的数放到它的右边，小于或等于它的数放到它的左边。
- 再对左右区间重复第三步，直到各区间只有一个数。
如上图所示快速排序的一个重要步骤是对序列进行以中轴数进行划分，左边都小于这个中轴数，右边都大于该中轴数，然后对左右的子序列继续这一步骤直到子序列长度为1。
下面来看某一次划分的步骤，如下图：
上图中的划分操作可以分为以下5个步骤：
- 获取中轴元素
- i从左至右扫描，如果小于基准元素，则i自增，否则记下a[i]
- j从右至左扫描，如果大于基准元素，则i自减，否则记下a[j]
- 交换a[i]和a[j]
- 重复这一步骤直至i和j交错，然后和基准元素比较，然后交换。
划分过程的代码实现如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
/// <summary> /// 快速排序中的划分过程 /// </summary> /// <param name="array">待划分的数组</param> /// <param name="lo">最左侧位置</param> /// <param name="hi">最右侧位置</param> /// <returns>中间元素位置</returns> private static int Partition(T[] array, int lo, int hi) { int i = lo, j = hi + 1; while (true) { //从左至右扫描，如果碰到比基准元素array[lo]小，则该元素已经位于正确的分区，i自增，继续比较i+1； //否则，退出循环，准备交换 while (array[++i].CompareTo(array[lo]) < 0) { //如果扫描到了最右端，退出循环 if (i == hi) break; } //从右自左扫描，如果碰到比基准元素array[lo]大，则该元素已经位于正确的分区，j自减，继续比较j-1 //否则，退出循环，准备交换 while (array[--j].CompareTo(array[lo]) > 0) { //如果扫描到了最左端，退出循环 if (j == lo) break; } //如果相遇，退出循环 if (i >= j) break; //交换左a[i],a[j]右两个元素，交换完后他们都位于正确的分区 Swap(array, i, j); } //经过相遇后，最后一次a[i]和a[j]的交换 //a[j]比a[lo]小，a[i]比a[lo]大，所以将基准元素与a[j]交换 Swap(array, lo, j); //返回扫描相遇的位置点 return j; } |
划分前后，元素在序列中的分布如下图：
二 实现
与合并算法基于合并这一过程一样，快速排序基于分割(Partition)这一过程。只需要递归调用Partition这一操作，每一次以Partition返回的元素位置来划分为左右两个子序列，然后继续这一过程直到子序列长度为1，代码的实现如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class QuickSort<T> where T : IComparable<T> { public static void Sort(T[] array) { Sort(array, 0, array.Length - 1); } private static void Sort(T[] array, int lo, int hi) { //如果子序列为1，则直接返回 if (lo >= hi) return; //划分，划分完成之后，分为左右序列，左边所有元素小于array[index]，右边所有元素大于array[index] int index = Partition(array, lo, hi); //对左右子序列进行排序完成之后，整个序列就有序了 //对左边序列进行递归排序 Sort(array, lo, index - 1); //对右边序列进行递归排序 Sort(array, index + 1, hi); } } |
下图说明了快速排序中，每一次划分之后的结果：
一般快速排序的动画如下：
三 分析
- 在最好的情况下，快速排序只需要大约nlgn次比较操作，在最坏的情况下需要大约1/2 n2 次比较操作。在最好的情况下，每次的划分都会恰好从中间将序列划分开来，那么只需要lgn次划分即可划分完成，是一个标准的分治算法Cn=2Cn/2+N，每一次划分都需要比较N次，大家可以回想下我们是如何证明合并排序的时间复杂度的。在最坏的情况下，即序列已经排好序的情况下，每次划分都恰好把数组划分成了0，n两部分，那么需要n次划分，但是比较的次数则变成了n, n-1, n-2,….1, 所以整个比较次数约为n(n-1)/2~n2/2.
- 快速排序平均需要大约2NlnN次比较，来对长度为n的排序关键字唯一的序列进行排序。 证明也比较简单：假设CN为快速排序平均花在比较上的时间，初始C0=C1=0，对于N>1的情况，有：其中N+1是分割时的比较次数， 表示将序列分割为0，和N-1左右两部分的概率为1/N, 划分为1，N-2左右两部分的概率也为1/N，都是等概率的。然后对上式左右两边同时乘以N，整理得到：
然后，对于N为N-1的情况：
