1. 算法描述

    快速排序(quick-sort)与前面介绍的归并排序(merge-sort)（见算法基础——算法导论(1)）一样，使用了分治思想。下面是对一个一般的子数组A[p~r]进行快速排序的分治步骤：

① 分解：数组A[p~r]被划分为两个子数组A[p~q]和A[q+1~r]，使得 A[q] 大于等于 A[p~q] 中的每个元素，且小于等于 A[q+1~r] 中的每个元素。（需要注意的是， A[p~q] 和 A[q+1~r] 可能为空）

② 解决：对子数组 A[p~q] 和 A[q+1~r] 递归调用本程序。

③ 合并：因为子数组都是原址排序的，所以不需要合并操作，此时的A数组已经是排好序的。

ps：所谓原址排序是指：在对组进行排序的过程中，只有常数个元素被存储到数组外面。

快速排序的核心思想其实很简单，即：在数组中，如果某元素均比自己前面的元素大（或等于），而比自己后面的元素小（或等于），则该元素处于“正确位置”。

下面给出伪代码：

可以看出，算法的关键是partiton方法的实现。下面给出它的算法实现：

直接看可能觉得很晕，我们结合实例看看它是如何工作的：

    上图(a~i)表示的是对子数组A[p~r] =[2,8,7,1,3,5,6,4]进行排序时，每次迭代之前数组元素和一些变量的值。

    我们可以初步看出，在i和j移动的过程中，数组被分成了三个部分（分别用灰色，黑色，白色表示），其中i和j就是分割线，并且浅灰部分的元素均比A[r]小，黑色部分的元素均比A[r]大（(i)图除外，因为循环完毕之后执行了exchange A[i+1] with A[j]）。

    我们再仔细分析一下具体细节：

    ① 首先看迭代之前的部分。它执行了x = A[r]，目的是把子数组A的最后一位作为一个“基准”，其他的所有元素都是和它进行比较。它在迭代过程中值一直都没改变。然后执行i = p –基准 1，此时i在子数组A的左端。

    ② 再看迭代部分。迭代时j从子数组A的开头逐步移至A的倒数第二位。每次迭代中，会比较当前j位置的值和“基准”的大小，如果小于或相等“基准”，就将灰色部分的长度增加1（i=i+1），然后把j位置的值置换到灰色部分的末尾（exchange A[i] with A[j]）。这样迭代下来，就能保证灰色部分的值都比“基准”小或相等，而黑色部分的值都比“基准”大。

    ③ 最后看迭代完成后的部分。就进行了一步 exchange A[i+1] with A[j]操作，就是把“基准”置换到灰色部分与黑色部分之间的位置。

    这样所有的操作下来，就产生了一个“临界”位置q，使得A[q]大于等于A[p~q]中的每个元素，而小于等于A[q+1~r]中的每个元素。

    更严格的，我们可以用以前介绍的循环不变式（见算法基础——算法导论(1)）来证明其正确性。但由于叙述起来比较麻烦，这里就不给出了。

    下面我们给出快速排序(quick-sort)算法的Java实现代码：