/*
先来看下快排
9.9 快速排序
事实上，不论是C++ STL、java SDK或者.NETFrameWork SDK等开发工具包中的源代码中都能找到它的某种实现版本。
快速排序算法是由图灵奖获得者TonyHoare设计出来的，他在形式化方法理论以及AL-GOL60编程语言的发明中都有卓越贡献，
是上世纪最伟大的计算机科学家之一，我们现在学习的这个快速排序算法，被列为20世纪十大算法之一。快去看下它到底有多牛吧。
希尔排序相当于直接插入排序的升级，他们同属于插入排序类
堆排序相当于简单选择排序的升级，他们同属于选择排序类
而快速排序其实就是我们前面认为最慢的冒泡排序的升级，他们都属于交换排序类，即他也是通过不断比较和移动交换来实现排序的，
只不过它的实现，增大了记录的比较和移动距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，
从而减少了总的比较次数和移动交换次数。
快排思想：
通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，
已到达整个序列有序的目的；快排的思想和二分查找有几分神似。
从字面上感觉不出它的好处来。假设现在要对数组{50,10,90,30,70,40,80,60,20}进行排序。我们通过代码的讲解来学习快速排序的精妙。
*/
快速排序算法详解
void quick_sort(vector<int> &nums, int left, int right){
if(left+1 >= right){ //最多有一个元素，无需排序
return;
}
int first = left, last = right-1, key = nums[first];
//通过一趟排序将待排记录分割成独立的两部分，其中一部分的值均比另一部分的值小；
while(first < last){
while(first < last && nums[last] >= key){
--last;
}
nums[first] = nums[last];
while(first < last && nums[first] <= key){
++first;
}
nums[last] = nums[first];
}
//再按这种方法对这两部分的数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列
nums[first] = key;
quick_sort(nums, left, first);
quick_sort(nums, first+1,right);
}