快速排序

快速排序是应用最广泛的排序算法，也是目前认为最好的一种内部排序方法（就平均时间而言）。它采用分治（divide-and-conquer）的策略，通过一趟排序将待排记录分割成独立的两个部分，使其中的一部分记录关键字均比另一部分记录关键字小（大），然后分别对两个部分继续进行排序，以达到整个序列有序。

快速排序的C/C++代码实现：

快速排序的平均时间复杂度为O(n㏒ⁿ)，相对于希尔排序，对于大（large）的随机顺序文件，快速排序比希尔排序快将近两倍。对于巨大（huge）文件，快速排序算法的性能是则是希尔排序的5~10倍。

快速排序在空间使用上需要一个小的辅助栈。对于快速排序来说，其最好的情况是每趟排序时都将待排序列均匀地分割成长度相接近的两个子序列，这样排序栈的最大深度将不超过㏒₂ⁿ+1（完全二叉树深度），且如果都先对长度短的子序列进行排序，那么栈的最大深度还可降为O(㏒ⁿ)。但如果碰到最坏的情况，比如文件已经排好序时，那么快速排序所有的划分都将退化，这不仅意味着执行时间上将为n²/2，而且栈所需要的空间也将是n。这对大文件来说是不可接受的，因为它可能使程序因为缺少内存空间而非正常结束。

快速排序对于寻找一些数字的中间数也很有用，寻找一些数字的中间数与排序有关但又不是排序的重要应用。一个解决办法就是先将这些数字排序，再找到中间数。但采用基于快速排序的寻找可以做的更好，它能使所需运行时间达到线性。具体的介绍可以参考《算法I-IV》（Robert Sedgewick著）。

快速排序的改进版本

从C. A. R. Hoare发布快速排序的那一刻起，快速排序的改进版本就不断的涌现。比如对于上面的程序，就还可以再做两点改进：1. 为了避免最坏情况的发生，在选取Pivot元素的时候，可以采用“三者取中法”（median-of-three method），即取待排序列中的最左边元素、中间元素和最右边元素，对这三个数排序，然后取它们的中间元素作为Pivot。2. 由于递归实现中程序多次因为小的子序列而调用自身，这影响程序的运行效率。因此当子序列已经很小时，可以中止递归的执行。在递归完成的最后再统一对它们采取一次插入排序。因为此时的序列已基本有序，因而插入排序效率非常高。对于中止的子序列长度的取法，通常是5~25之间的值，一个比较好的值是9（参考《计算机程序设计艺术》 Donald E. Knuth著）。通常，对这两点的改进就可以有效提高快速排序20%~25%的效率。

竞争的排序算法

快速排序的最直接竞争者是堆排序（Heap Sort）。堆排序通常比快速排序稍微慢，但是最坏情况的执行时间总是O(n㏒ⁿ)。快速排序经常比较快，但最坏情况下时间复杂度却为O(n²)。此外快速排序空间的使用O(㏒ⁿ)也要比堆排序O(1)要高。

快速排序也与归并排序（Merge Sort）竞争，这是另外一种递归排序算法，它也有最坏情况O(n㏒ⁿ)执行时间的优势，并且归并排序是稳定的排序方法。归并排序的主要缺点是在最佳情况下仍需O(n)的额外辅助空间。