快速排序

C++ STL中提供了sort（）函数，但对于学习理解快速排序的思想，还是得明白快速排序手写模板的具体运用。

时间复杂度：O(n*logn)。
空间复杂度：O（n）。

具体思想是选择一个一个枢纽进行比较，从两端开始寻找。左端点找到一个比枢纽大的值，右端点找到一个比枢纽小的值，进行交换。然后左右递归两端，类似于二叉树的先序遍历。

对于枢纽的选择是具有不确定性的，可以选择任意一个断点值。为了方便计算一般选择左端点、右端点或者中间值。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N],n;
void quick_sort(int *a,int l,int r)
{
    int i = l-1,j = r+1;//预处理 因为循环使用的do while循环
    int x = a[(l+r)/2];//定义一个枢纽
    if( l >= r)//递归终止条件
        return;
    while(i < j)
    {
        do i++;while(a[i] < x);
        do j--;while(a[j] > x);//找到两个符合的数值进行交换
        if(i < j)
            swap(a[i],a[j]);
    }
    quick_sort(a,l,j);//递归遍历
    quick_sort(a,j+1,r);
}
int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
        scanf("%d",&a[i]);
    quick_sort(a,0,n-1);
    for(int i = 0;i < n;i++)
        printf("%d ",a[i]);
    return 0;
}