主要内容
快速排序概述
快速排序与合并排序还有其他几种不同。快速排序直接利用原数组空间进行排序。还有， 其最坏情况的运行时间与选择排序和插入排序一样糟糕：
因此，为什么在合并排序至少一样好时考虑快速排序？ 这是因为隐藏在快速排序的大Θ计数法中的常数是很好的。 实际上，快速排序比合并排序性能更好，它的性能大大超过选择排序和插入排序。
以下是快速排序如何使用分而治之的方法。 与合并排序一样，考虑排序子数组
array[p..r]，其中最初的子数组是array[0..n-1]。- 通过在子阵列的
array[p..r]中选择任何元素来分隔 。给这个元素命名为枢轴。重新排列array[p..r]中的元素，以便array[p..r]中小于或等于枢的所有元素都在它的左边，所有大于枢的元素都是在它的右边。 我们称这个程序为 分区。 在这一点上，枢轴左侧的元素相对于彼此的顺序无关紧要，并且对于枢轴右侧的元素也是如此。 我们只关心每个元素位于枢轴正确的一侧。作为一个练习，我们总是选择子阵列中最右边的元素array [r]作为枢轴。 因此，例如，如果子阵列由[9,7,5,11,12,2,14,3,10,6]组成，那么我们选择6作为枢轴。 分区后，子阵列可能看起来像[5,2,3,6,12,7,14,9,10,11]。 设q是枢轴结束的索引。 - 通过递归排序子数组
array [p..q-1]（枢轴左边的所有元素，必须小于或等于枢轴）和array[q+1..r]（枢轴右侧的所有元素，必须大于枢轴）来治理。 - 无所事事地结合。 治理步骤中的递归排序之后，我们就完成了。 为什么？ 在数组
array[p..q-1]中，数组左侧的所有元素都小于或等于枢都排序好了，并且数组中array[q+1..r]的所有元素都大于枢的也都排序好了。array[p..r]中的元素自然就排好序了！思考一下我们的例子。 在递归地将子数组排序到枢轴的左侧和右侧之后，枢轴左侧的子阵列是[2,3,5]，并且枢轴右侧的子阵列是[7,9,10,11,12,14]。 所以子阵列有[2,3,5]，接着是6，接着是[7,9,10,11,12,14]。 子阵列已排序。
基本情况是少于两个元素的子数组，就像在合并排序中一样。 在合并排序中，您永远不会看到没有元素的子数组，但是在快速排序中可以发现有这种情况的存在， 比如子数组中所有的其他元素都小于（或者大于）枢。
让我们回到治理步骤并逐步完成子数组的递归排序。 在第一个分区之后，我们有[5,2,3]和[12,7,14,9,10,11]的子数组，以6为枢轴。
为了对子数组[5,2,3]进行排序，我们选择3作为枢轴。 分区后，我们有[2,3,5]。 当我们将子数组[5]放到枢轴的右侧，枢轴左侧的子数组[2]， 这两个都是基本情况（只有一个元素）。
为了对子阵列[12,7,14,9,10,11]进行排序，我们选择11作为枢轴，导致枢轴左侧为[7,9,10]，右侧为[14,12]。 在对这些子阵列进行排序后，我们得到[7,9,10]，然后是11，接着是[12,14]。
以下是整个快速排序算法的展开。 数组中蓝色的位置在之前的递归调用中已成为过枢，因此不会检查或再次移动这些位置中的值：