快速排序的优化算法

以前自己写过快速排序，但是代码看起来比较臃肿，计算分离点的时候用了2重循环来回判断，时间复杂度比较高。今天在看《算法导论》的时候，书上的方法非常经典，巧妙利用一个标志变量就实现了只用一重循环来partition。

           快排的基本原理是:定义一个基准点base，然后通过遍历整个序列，把小于base的放在左边，大于base的放在右边，然后对划分后的两段序列进行递归调用，递归的条件是start=end时，递归结束，然后工作栈不断返回，结束排序。通过一个标志变量i来优化的，虽然时间复杂度减少不多，但是当序列特别长的时候，能够更加节省时间。

           以下是算法代码和测试代码：

#include <stdio.h>
#include <conio.h>

//函数原型
void swap(int *a,int *b);
int partition(int A[],int start,int end);
void quick_sort(int A[],int start,int end);
//测试代码
int main()
{
    int test[11]={-1,2,5,6,7,8,9,1,4,3,10};
    quick_sort(test,1,9);
    for(int i=1;i<11;i++)
        printf("%d ",test[i]);
    getch();
}

//划分区域
int partition(int A[],int start,int end)
{
    int base=A[end];//以最后一个数作为划分的基点
    int i=start-1; //i表示比base小且最靠右的数的下标，这里很巧妙的利用i来消除了另外一次循环。
    for(int j=start;j<end;j++)
    {
        if(A[j]<=base)
        {
            i++;
            swap(&A[i],&A[j]);
        }
    }
    swap(&A[i+1],&A[end]);
    return i+1;
}


void quick_sort(int A[],int start,int end)
{
    //注意这里不要忘记递归结束的条件
    if(start<end)
    {
        int t=partition(A,start,end);
        quick_sort(A,start,t-1);
        quick_sort(A,t+1,end);
    }
}

//交换
void swap(int *a,int *b)
{
    int temp=*a;
    *a=*b;
    *b=temp;
}