快速排序，Quick Sort。
采用了经典的分治思想：每次确定一个元素的位置，并将序列分为两个子序列：小于等于该元素、大于等于该元素。问题转为分别对刚得到的两个序列进行处理，直到序列长度为1.
Partition函数是比较重要的，这里采用了和算法导论类似的想法：每次随机从中抽取一个元素A，将其与序列尾部元素交换。从头向后扫描，保存两个index：small、index。small逐渐加一，标识比A小的元素应放的坐标。index向后扫描，每当发现小于A的元素，就令small+1，并交换index 和 small所指元素。最后交换small+1和A（即序列尾部元素）。
最后用递归实现分治。参考代码如下（代码参考自《剑指Offer》以及《算法导论》）：
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
int Partition(int *a, int length, int start, int end)
{if (a == NULL || start<0 || end>=length){return -1;}srand(time(NULL));int index = rand()%(end-start)+start;swap(a[index], a[end]);int small = start - 1;for (index = start; index <= end; index++){if (a[index] < a[end]){small++;if (index!=small)swap(a[small], a[index]);}}small++;swap(a[small], a[end]);return small;
}void QSort(int* a, int length, int start, int end)
{if (start == end)return;int p = Partition(a, length, start, end);if (p > start)QSort(a, p-start , start, p - 1);if (p < end)QSort(a, end-p, p + 1, end);}void Print(int *a, int len)
{for (int i = 0; i < len; i++)cout << a[i] << " ";
}int main()
{srand(time(NULL));const int maxLen=10;const int maxNum = 1000;int *a = new int[maxLen];for (int i = 0; i < maxLen; i++){a[i] = rand() % maxNum;}QSort( a , maxLen, 0, maxLen - 1);Print(a, maxLen);cout << endl;return 0;
}