快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想—-分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此结合网上资料对快速排序作了进一步的说明：挖坑填数+分治法：
先来看实例吧，定义下面再给出（最好能用自己的话来总结定义，这样对实现代码会有帮助）。
以一个数组作为示例，取区间中间数为基准数。
初始时，i= 0; j= 7; 中间值32作为基准值;交换中间值和尾元素，将基准值72挪到数组最后去，并将基准值赋值给1个临时变量X保存；
此刻数组结构如下：
由于已经将32保存到X中，可以理解成在数组a[7]上挖了个坑，可以将其它数据填充到这来。
从l开始向前找一个比X大或等于X的数。当l=1，符合条件，将a[1]=34挖出再填到上一个坑a[7]中同时j– 这样一个坑a[7]就被搞定了，此时数组如下：
但又形成了一个新坑a[1]，这怎么办了？j–，从后向前找到1个小于基准值的数据，填a[1]的坑
再重复上面的步骤，先从前向后找，再从后向前找，后续图解如下：
对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
3．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
最后代码总结如下：
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::begin;
using std::end;
template <typename T>
void swap(vector<T> &v,int index1,int index2)
{
T temp = v[index1];
v[index1] = v[index2];
v[index2] = temp;
}
int selectPivot(int left,int right)// 选择轴值，参数left,right分别表示序列的左右端下标
{
return (left + right)/2; // 选择中间记录作为轴值
}
template <typename T>
int partition(vector<T> &v,int left,int right)// 分割函数，分割后轴值已到达正确位置
{
int l = left;
int r = right;
T temp = v[right];// l为左指针，r为右指针
while(l != r)// 开始分割,l,r不断向中间移动，直到相遇
{
// l指针向右移动，直到找到一个大于轴值的记录
while(v[l] <= temp && l < r)// 这里也可以把"<="改写为"<"，反正不稳定
{
l++;
}
if(l < r)// 若l,r尚未相遇，将逆置元素换到右边的空位
{
v[r] = v[l];
r--;// r指针向左移动一步
}
// r指针向左移动，直到找到一个小于等于轴值的记录
while(v[r] > temp && r > l)// 这里也可以把">"改写为">="，减少记录移动
{
r--;
}
if(l < r)
{
v[l] = v[r];// 若l,r尚未相遇，将逆置元素换到左边的空位
l++;// l指针向右移动一步
}
}
v[l] = temp;// 把轴值回填到分界位置l上
return l;// 返回分界位置l
}
template <typename T>
void quickSort(vector<T> &v,int left,int right)
{
if(left >= right)// 如果子序列中只有0或1个记录，就不需排序
{
return;
}
else
{
int pivot = selectPivot(left,right);// 选择轴值
swap(v,pivot,right);// 分割前先将轴值放到数组末端
pivot = partition(v,left,right);// 分割后轴值已到达正确位置
quickSort(v,left,pivot-1);// 对轴值左边的子序列进行递归快速排序
quickSort(v,pivot+1,right);// 对轴值右边的子序列进行递归快速排序
}
}
template <typename T>
void print(vector<T> &v)
{
for(int i = 0; i < v.size(); i++)
{
cout << v.at(i) << "\t";
}
cout << endl;
}
const int SIZE = 8;
int main()
{
vector<int> v;
int value;
time_t t;
srand((unsigned) time(&t));
for(int i = 0; i < SIZE; i++)
{
value = rand()%1000;
v.push_back(value);
}
cout << "排序前的数组"<<endl;
print(v);
quickSort(v,0,v.size() -1);
cout << "排好序的数组"<<endl;
print(v);
system("pause");
return 0;
}