排序算法之－－快速排序
快速排序
分而治之方法还可以用于实现另一种完全不同的排序方法，这种排序法称为快速排序（quick sort）。在这种方法中， n 个元素被分成三段（组）：左段l e f t，右段r i g h t和中段m i d d l e。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此l e f t和r i g h t中的元素可以独立排序，并且不必对l e f t和r i g h t的排序结果进行合并。m i d d l e中的元素被称为支点( p i v o t )。图1 4 - 9中给出了快速排序的伪代码。
/ /使用快速排序方法对a[ 0 :n- 1 ]排序
从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点
把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点
递归地使用快速排序方法对left 进行排序
递归地使用快速排序方法对right 进行排序
所得结果为l e f t + m i d d l e + r i g h t
图14-9 快速排序的伪代码
考察元素序列[ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ]。假设选择元素6作为支点，则6位于m i d d l e；4，3，1，5，2位于l e f t；8，7位于r i g h t。当left 排好序后，所得结果为1，2，3，4，5；当r i g h t排好序后，所得结果为7，8。把right 中的元素放在支点元素之后， l e f t中的元素放在支点元素之前，即可得到最终的结果[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]。
把元素序列划分为l e f t、m i d d l e和r i g h t可以就地进行（见程序1 4 - 6）。在程序1 4 - 6中，支点总是取位置1中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。
程序14-6 快速排序
template
void quicksort(t*a, int n)
{// 对a[0:n-1] 进行快速排序
{// 要求a[n] 必需有最大关键值
quicksort(a, 0, n-1);
template
void quicksort(t a[], int l, int r)
{// 排序a [ l : r ]， a[r+1] 有大值
if (l >= r) return;
int i = l, // 从左至右的游标
j = r + 1; // 从右到左的游标
t pivot = a[l];
// 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换
while (true) {
do {// 在左侧寻找>= pivot 的元素
i = i + 1;
} while (a[i] < pivot);
do {// 在右侧寻找<= pivot 的元素
j = j - 1;
} while (a[j] > pivot);
if (i >= j) break; // 未发现交换对象
swap(a[i], a[j]);
}
// 设置p i v o t
a[l] = a[j];
a[j] = pivot;