算法模板之排序算法

快速排序

其实现排序的原理是：每轮选择一个数作为基准数，每轮实现将大于改基准数的值放到基准数的右侧，小于的放到其左侧，然后将数组在基准数处截断，分成两段，同样执行该过程，直到最后分出来的一段的长度为1，即可停止。

这样将数组分出来的每一个小段都进行了排序，也就实现了数组整体的排序。

void quick_sort(int num[],int l,int r){
    if(l>=r)return ;
    int i=l-1,j=r+1;
    int x=num[l+r>>1];//x是每轮比较的参考数值
    while(i<j){
        do i++;while(num[i]<x);
        do j--;while(num[j]>x);
        if(i<j)swap(num[i],num[j]);//swap()函数是交换函数
    }
    quick_sort(num,l,j);
    quick_sort(num,j+1,r);
}
void swap(int &a,int &b){
    int c=a;
    a=b;
    b=c;
}