高速排序

学快排的时候參考了这篇博客http://blog.csdn.net/morewindows/article/details/6684558，博主关于快排的解说通俗易懂，表示感谢。算法原书的快排切分代码写的有点啰嗦，刚看到 j=hi+1那一行还以为写错了，结果后面用的是 a[--j]，无语。只是后文，作者自己也说部分代码冗余的，仅仅是为了提醒读者注意訪问数组时不要越界。顿时感觉国外的作者写书真的非常用心。

#include <iostream>
using namespace std;

// 快排的关键在于切分
int partition(int a[],int low,int high){
    // 取a[low]作为切分元素
    int p=a[low];
    int i=low;
    int j=high;
    while(i<j){
        // 先从右往左找比p小的元素
        while(i<j && a[j]>=p) j--;
        if(i<j){
            a[i]=a[j];
            i++;
        }
        // 再从左往右找比p小的元素
        while(i<j && a[i]<p) i++;
        if(i<j){
            a[j]=a[i];
            j--;
        }
    }
    a[i]=p;
    return i;
}

void quick_sort(int a[],int low,int high){
    if(low>=high) return;
    int j=partition(a,low,high);
    quick_sort(a,low,j-1);
    quick_sort(a,j+1,high);
}

void show(int a[],int n){
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main(){
    int a[10]= {3,6,2,7,9,0,8,1,4,5};
    show(a,10);
    quick_sort(a,0,9);
    show(a,10);
    return 0;
}