学步园

快速排序是冒泡排序的一种改进形式，通过将待排序数据分解成大小两组，然后递归分解下去，直到分解为一个元素为止来完成排序。
快速排序的关键就是分组，即如何把数组分为大于中心轴点和小于中心轴点的两部分；
分组实现步骤如下：假设数组a[left,right]
1、选择中心轴点，这里选取数组的最后一个元素a[right]为中心轴点；
2、遍历数组，范围为[left,right-1]，变量i，j；初始值i=left,j=left；
3、如果a[j]>a[right]，就将a[j]与a[i++]交换
4、最后将a[i]与a[right]交换，就实现分组；

算法具体代码如下：

void inline swap(int &a,int &b)
{
    if(a==b)
    {
        return ;
    }
    a=a^b ;
    b=a^b ;
    a=a^b ;
}

#define LEN 23
int Partition(int a[],int left,int right)
{
    int pivot=right ;
    int i=left ;
    int j=left ;
    for(j=left;j<right;j++)
    {
        if(a[j]<a[pivot])
        {
            swap(a[j],a[i++]) ;//理解这一步是关键，为什么是a[j]和a[i++]交换呢？
        }
    }
    swap(a[i],a[pivot]) ;

    for(int m=0;m<LEN;m++)
    {//打印输出，便于调试
        cout<<a[m]<<"," ;
    }
    cout<<endl;
    return i ;
}

void QuikSort(int n[],int left,int right)
{
    int tmp ;
    if(left<right)
    {
        tmp=Partition3(n,left,right) ;
        QuikSort(n,left,tmp-1) ;
        QuikSort(n,tmp+1,right) ;
    }
}
int main()
{
    int n[]={ 12, 2, 12, 2, 9, 11, 34, 54,5,4,3,2,1,10,9,8,7,6,5,4,3,2,1 };
    QuikSort(n,0,22) ;
    return 0 ;
}