快速排序是一种划分交换的方法，它采用分治法进行排序。 基本思想：任取待排序序列中的某个元素作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个序列：左边都小于基准元素，右边都大于或等于，基准元素在这两个序列中间，然后分别对这两个子序列重复上述操作，知道所有元素都排在相应位置为止。 我们可通过图来理解：
首先实现大的框架,递归的实现很简单就是首先对整个区间进快排，然后分成两个小区间快排，最后再转化成递归问题进行快排。
void QuickSort(T* arr,int left,int right) { if (left < right) { int pivotpos = Partition(arr, left, right); QuickSort(arr, left, pivotpos - 1); QuickSort(arr, pivotpos + 1, right); } }分析单趟排序： 1. 左右指针法 左右指针，左边指针++找比基准元素大的位置，右边指针–找比基准元素小的位置，进行交换，直到left==right退出循环，把基 元给在这个位置。 对于快速排序有的优化思路：
三数取中法:为了防止出现我们所选取的可以是最大的或者最小的，造成一个快速排序的效率接近了冒泡排序的效率。为了更加高效，就需要使用三数取中法。
//三数取中法 template<class T> int Getmid(T* arr, const int left,const int right) { int mid = left + ((right - left) >> 1); int k = left; if (arr[mid] < arr[k]) k = mid; if (arr[right] < arr[k]) k = right; if (k != left) swap(arr[k], arr[left]); if (mid != right&&arr[mid] < arr[right]) swap(arr[mid], arr[right]); return arr[right]; } template<class T> int Partition(T* arr, const int begin, const int end) { int left = begin; int right = end; int mid = Getmid(arr, left, right); T key = arr[end]; while (left < right) { while (left < right&&key>=arr[left]) { ++left; } while (left < right&&arr[right]>=key) { --right; } if (arr[left]>arr[right]) { swap(arr[left], arr[right]); } } swap(arr[left], arr[end]); return left; }2. 前后指针法 给cur=left;prev=cur-1; 然后让cur找比基准元素小的，找到后对prev++；然后进行交换，当然得先进行判断，cur！=prev才能进行交换.
template<class T> int Partition(T* arr, int left, int right) { int cur = left; int prev = cur - 1; T key = arr[right]; while (cur < right) { while (key>arr[cur]&&++prev != cur) swap(arr[cur], arr[prev]); cur++; } swap(arr[++prev], arr[right]); return prev; }3. 挖坑法
template<class T=int> int Partition(T* arr, int begin, int end) { int left = begin; int right = end; int mid = Getmid(arr, begin, end); T tmp = arr[end]; while (left < right) { while (left < right&&arr[left]<=tmp) { ++left; } if (left < right) arr[right--] = arr[left]; while (left < right&&arr[right]>=tmp) { --right; } if (left < right) arr[left++] = arr[right]; } //此时left==right、填坑 arr[left] = tmp; return left; }4. 效率 快速排序在优化以后效率可以达到O（logN）。在同为O(N*logN)的几种排序方法中效率较高
