前面两个小节，我们分别介绍了冒泡排序，直接插入排序，在我们本节讲解一种更加高效的排序方法，快速排序，也即是常说的快排。
1、算法思想
实际上，快排是对冒泡排序的一种改进，采用分而治之的思想。
在待排序表 A[1,2…n]中选取一个基准值pivot（通常选取序列首元素）;
通过一趟排序操作将待排序表分为独立的两部分A[1,2…k-1]，A[k+1,…n]。
其中A[1,2…k-1]都是比基准值小的元素，A[k+1,…n]都是比基准值大的元素。
而基准值pivot通过一趟排序确定了最终的位置，然后就是对A[1,2…k-1], A[k+1,…n]这两部分，递归的进行上述操作。
2、优缺点
优点：
平均时间资源消耗O(nlogn) 没有冒泡排序，直接插入排序大。
有很多优化方法，如递归划分得到的子序列的规模较小的时候，不要再递归调用快排，或者尽量选取一个可以讲数据中分的基准元素。
缺点：
需要额外的空间来保存递归的信息，平均空间复杂度O(logn)
不稳定，可能会使得某些元素的相对位置发生变化。
3、关键点
主要操作两部分：根据基准元素划分块，在划分的块上进行递归操作。
无论是划分块操作，还是在块上进行排序的操作，都用到两个控制变量，left 和 right。(控制结束，当两个变量相遇的时候结束)
每一趟排序后将一个元素（基准元素）放到最终的位置上
4、程序代码（c++）
例子：输入一个有10个元素的数组，并对其进行快速排序，最后数组为升序。
/**************************************************************************** @file Quick_sort.cpp* @author Shawn* @date 31 Dec 2018* @remark 31 Dec 2018* @theme Quick Sort***************************************************************************/
# include<iostream>
using namespace std;
void quicksort(int[], int, int);
int partition(int[], int, int);
int main()
{
int array [] = {
55,2,6,4,32,12,9,73,26,37};int len = sizeof(array) / sizeof(int);cout<<"输入的原始序列: ";for(int i=0; i<len; i++) // 输出原序列cout<<array[i]<<",";cout<<endl<<endl;quicksort(array,0, len-1); // 调用排序函数cout<<" ----快速排序结果---- " << endl;for(int i=0; i<len; i++)cout<<array[i]<<",";cout<<endl;return 0;
}void quicksort(int a[], int left, int right) // 快排算法
{
if(left<right){
int pivotpos = partition(a,left,right); // 排好序的基准元素quicksort(a,left, pivotpos-1); // 根据基准元素划分的块,递归quicksort(a,pivotpos+1,right); // 根据基准元素划分的块，递归}}int partition(int a[], int left, int right) // 划分算法，核心
{
int pivot = a[left];while(left<right) // 两个相遇结束{
while(left<right && a[right] >= pivot) --right; //从每一部分的最后一位开始检查if(left<right) a[left++] = a[right]; // 将比基准小的放在基准左侧 结合while说明 right小于pivotwhile(left<right && a[left] <= pivot) ++left; // 从每一部分的最初一位开始检查if(left<right) a[right--] = a[left];// 将比基准大的放在基准右侧结合while说明 left大于pivot}a[left] = pivot; // 将基准元素放在最终的位置上，使得左边都是比他小的，右边都是比他大的return left;
}
下一讲 选择排序