快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要笑，然后在按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
Partition1：（传统法）
定义一个标准key,此处key选择数组的最后面a[right]，然后定义begin和end，分别从前往后找比key大的和从后往前找比key小的，找到就进行交换，最后将数组变为以key为界的两个数组，进行递归
int Partition1(int *a, int left, int right){ assert(a); int begin = left, end = right - 1, key = a[right]; while (begin < end) { //找比key大的 while (a[begin] <= key && begin < end) { begin++; } //找比key小的 while (a[end] >= key && end > begin) { --end; } //找到了进行交换 if (begin < end) { swap(a[begin], a[end]); } } //将key放在两个数组之间 if (a[begin] > a[right]) { swap(a[begin], a[right]); return begin; } //只进行left—>right-1的递归 else { return right; }}void QuickSort1(int *a, int left, int right){ assert(a); if (right > left) { int boundary = Partition1(a, left, right); QuickSort1(a, left, boundary - 1); QuickSort1(a, boundary + 1, right); }} Partition2：
依然是在数组中找一个标准key=a[right]，定义prev和cur（初始cur - 1 = prev），分别向前指向比key小的和比key大的，逐次进行交换，直到数组最后面。
int Partition2(int *a, int left, int right){ assert(a); int cur = left, prev = left - 1, key = a[right]; while (cur < right) { //a[cur] < key && (++prev) != cur) { swap(a[prev], a[cur]); } ++cur; } //最终将数组分成以key为界的两个数组 swap(a[++prev], a[right]); return prev;}void QuickSort2(int *a, int left, int right){ assert(a); if (right > left) { int boundary = Partition2(a, left, right); QuickSort2(a, left, boundary - 1); QuickSort2(a, boundary + 1, right); }} Partition3：挖坑补位法
定义key=a[right] (任意)，此时a[right]就相当于是一个没有数据的坑，begin（初始）从前往后找比key大的，找到后就将该数据填充到a[right]中，此时begin位置就变成了坑，end从后往前找小的，找到了就填充到上一个坑，最终当begin=end时，将key放进去，数组又变成了以key 为界的两个数组。
int Partition3(int* a, size_t left, size_t right){ assert(a); int begin = left, end = right, key = a[end]; while (begin < end) { //begin向前找比key大的 while (begin < end && a[begin] <= key) { begin++; } //填坑 if (begin < end) { a[end] = a[begin]; } //end从后向前找比key小的 while (end > begin && a[end] >= key) { end--; } //填坑 if (end > begin) { a[begin] = a[end]; } } //最终将数组分成以key为界的两个数组 a[begin] = key; return begin;}void QuickSort3(int *a, int left, int right){ assert(a); if (right > left) { int boundary = Partition3(a, left, right); QuickSort3(a, left, boundary - 1); QuickSort3(a, boundary + 1, right); }} 优化法：（三数取中法）
当key为最大最小时，递归次数明显变大（效率低），所以尽量将key设置适中。
int GetMidIndex(int* a, size_t left, size_t right){ int mid = left + (right - 1); if (a[left] < a[right]) { if (a[mid] < a[left]) return left; else if (a[mid] < a[right]) return mid; else return right; } else { if (a[mid] < a[right]) return right; if (a[mid] < a[left]) return left; else return mid; }} 非递归实现QuickSort
void QuickSort4(int* a, size_t left, size_t right){ assert(a); stack s; if (left < right) { int boundary = Partition3(a, left, right); if (left < boundary - 1) { s.push(left); s.push(boundary - 1); } if (boundary + 1 < right) { s.push(boundary + 1); s.push(right); } while (!s.empty()) { int end = s.top(); s.pop(); int begin = s.top(); s.pop(); boundary = Partition2(a, begin, end); if (begin < boundary - 1) { //左边界在下，右边界在上。 s.push(begin); s.push(boundary - 1); } if (boundary + 1 < end) { s.push(boundary + 1); s.push(end); } } }}