前言
快速排序采用了分治法，即将原问题划分成为若干个规模更小且与原问题相似的子问题，然后递归地解决这些子问题，最后将他们组合起来。
快速排序的思想是：假设数据元素存放在数组L中，当前序列为L[left]~L[right]，left和right是当前序列的上下界；在序列中，任选一个数据元素L[pos]（一般选择L[left]，并成为枢轴）作为基准元素；然后，依次从序列的两端交替向序列中间扫描，将序列中关键字小于L[pos]的元素移动到pos的左边，大于L[pos]的元素移动到pos的右边，这样经过一趟快速排序之后，序列就被基准元素划分为了左右两个子序列L[left]~L[pos-1]和L[pos+1]~L[right]，并且左端序列中所有数据元素均小于基准元素，右边的所有元素都大于基准元素，这样基准元素的位置就确定好了。之后将切分开来的子序列重复上面的过程，直到left<right条件不满足，算法结束。
1. 编码
template<typename T> struct Disp
{
void operator()(T value)
{
cout << value << "\t";
}
};
int Partition(std::vector<int>& vec, int left, int right)
{
int base_pos = left; //选择left的坐标为基准元素
int temp(vec[left]);
while(left != right) //从数组的两边向中间扫描
{
//从右边开始寻找，直到找到第一个小于基准元素的坐标
while(left<right && temp<=vec[right]) --right;
if(left < right)
{
vec[left] = vec[right];
}
//从左边开始寻找，直到找到第一个大于基准元素的坐标
while(left<right && temp>=vec[left]) ++left;
if(left < right)
{
vec[right] = vec[left];
}
}
//最终将基准数归位
//vec[base_pos] = vec[left];
vec[left] = temp;
return left;
}
void my_QuikSort(std::vector<int>& vec, int left, int right)
{
if(left <= right) //待排序的元素至少有两个的情况
{
int break_pos = Partition(vec, left, right);
my_QuikSort(vec, left, break_pos-1); //对基准元素左边的元素进行递归排序
my_QuikSort(vec, break_pos+1, right); //对基准元素右边的进行递归排序
}
}
void QuikSort(std::vector<int> vec)
{
int len(vec.size());
if(len == 0) return;
cout << "display origin array:" << endl;
for_each(vec.begin(), vec.end(), Disp<int>()); //打印原始的数据
//快速排序
my_QuikSort(vec, 0, len-1);
cout << "\narray sorted:" << endl;
for_each(vec.begin(), vec.end(), Disp<int>());
}
