7，快速排序：
快速排序与归并排序还是有区别的，归并排序的计算量主要消耗的是有序子向量的归并操作，而子向量的划分却几乎不耗时间。
快速排序算法虽然能确保，划分出来的子问题相互独立，并且其规模总和保持渐进不变，但不能保证两个子问题的规模大体相当，甚至有可能不平衡。
快速排序算法实现的三种方法：
一：（1）左右指针法的思想：
（2）左右指针实现代码：
int PartSort(int* a, int left, int right) { int key = a[right]; int begin = left; int end = right - 1; while (begin < end) { while (a[begin]<key&&begin<end) { ++begin; } while (a[end]>key&&begin < end) { --end; } swap(a[begin], a[end]); } swap(a[begin], a[right]); } void QuickSort(int* a, int left, int right)//left与right区间 { assert(a); if (left < right) { int div = PartSort(a, left, right);//单趟排序，div为key值 QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); } }二：挖坑法：（1）挖坑发实现的思想如图所示：
（2）挖坑法实现的代码：
int PartSort(int* a, int left, int right) { int key = a[right]; while (left < right) { while (left < right&&a[left] < key) { ++left; } a[right] = a[left]; while (left < right&&a[right] <= key) { --right; } a[left] = a[right]; } a[left] = key; } void QuickSort(int* a, int left, int right) { assert(a); if (left < right) { int div = PartSort(a, left, right); QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); } }三：前后指针法（1）前后指针法思想：
（2）前后指针法的代码：
int PartSort(int* a, int left, int right) { int cur = left; int prev = left - 1; int key = a[right]; while (cur < right) { if (a[cur] < key&&++prev != cur) { swap(a[cur], a[prev]); } ++cur; } swap(a[++prev], a[right]); return prev; } void QuickSort(int* a, int left, int right) { assert(a); if (left < right) { int div = PartSort(a, left, right); QuickSort(a, left, div - 1); QuickSort(a, div + 1, right); } }