quicksort：分治思想。
分解：数组A[p, r)被划分成两个子数组A[p..q) 和 A[q+1, r)，使得A[p..q)中的每个元素小于等于A[q], A[q]也小于A[q+1..r)中的每个元素。q是划分过程要返回的结果。
解决：递归调用quicksort，对子数组A[p..q) 和 A[q+1, r)进行排序。
合并：因为子数组都是原址排序的，所以不需要合并操作：A[p..r)已经有序。
代码数组下标从0开始，并且所有函数使用左闭右开区间。与算法导论第三版书上的伪代码不同的部分在注释标出。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <cstdlib>
inline void swap(int &a, int &b)
{ int t = a; a = b; b = t; }
int partition(int *a, int p, int r) { //对 a[p, r) 原址重排
int x = a[r-1]; //a[r] ==> a[r-1]
int i = p - 1;
for (int j = p; j < r - 1; ++j)
if (a[j] <= x) {
++i;
swap(a[i], a[j]);
}
swap(a[i+1], a[r-1]);
return i + 1;
}
void quicksort(int *a, int p, int r) { //调用quicksort(a, 0, n),不是(a, 0, n-1)，区间a[0, n)
if (p < r - 1) { //(p < r) ==> (p < r - 1)
int q = partition(a, p, r);
quicksort(a, p, q); //(a, p, q-1) ==> (a, p, q)
quicksort(a, q+1, r);
}
}
int main()
{
srand(time(NULL));
int n;
while (scanf("%d", &n)) {
int a[n];
for (int i = 0; i < n; ++i)
a[i] = rand() % n;
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
quicksort(a, 0, n);
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
}
}
随机测试几万组数据与stl 的sort产生结果一致。