快速排序
快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
1. Hoare 版本
简单来说就是选某个元素为基准值（这里先默认第一个），然后把比基准值小的都放到基准值的左边，比基准值大的都放到基准值的右边。
以下图为例：
先以 6 为基准，然后左边找大，右边找小，之后互换。进行这么一趟后，6 左边就都比它小，右边都比它大。然后以 6 为分界线，再分成两个区间，类似于二叉树。
void QuickSort(int* a, int left, int right) {
if (left >= right) return; // 区间不存在时直接返回
int keyi = left;
int begin = left, end = right;
while (begin < end) {
// 从右向左找小于基准的值
while (begin < end && a[end] >= a[keyi]) end--;
// 从左向右找大于基准的值
while (begin < end && a[begin] <= a[keyi]) begin++;
Swap(&a[begin], &a[end]);
}
Swap(&a[keyi], &a[end]);
QuickSort(a, left, end - );
QuickSort(a, end + , right);
}
