前言

【算法导论描述】：快速排序在输入为n个数的数组，其最坏时间复杂度为$Θ(n^2)$，不过快速排序仍是实际排序应用中最好的选择，它的平均性能很好，期望时间复杂度为$Θ(nlgn)$，而且$Θ(nlgn)$中隐含的常数因子非常小，除此之外，快速排序很是一个能够进行原址排序的算法，不需要额外地申请空间，甚至在虚存环境也能很好地工作。

快速排序是采用分治策略的算法，有“分解”，”解决“，”合并“这三个过程，不过快速排序是进行原址排序的，因此不需要合并操作。

快排的关键点主要在于找那个划分点，你可以选择第一个，最后一个或者是随机选择一个作为划分点将数组划分为两个，一个小于等于划分点的值，另一个数组则反之。

快排C/C++实现

#include<cstdio>

void swap(int &a,int &b)
{
    int tmp=a;
    a=b;
    b=tmp;
}

int Partition(int A[],int L,int R)      //划分点选取最后一个
{
    int x=A[R];
    int i=L-1;
    for(int j=L;j<=R-1;j++)
    {
        if(A[j]<=x){
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[R]);
    return i+1;
}

void QuickSort(int A[],int Left,int Right)
{
    if(Left<Right)      //数组只剩下一个不需要再划分了 
    {
        int w=Partition(A,Left,Right);
        QuickSort(A,Left,w-1);
        QuickSort(A,w+1,Right);
    }
}

int main()
{
    int N;
    scanf("%d",&N); 
    int *A=new int[N];
    for(int i=0;i<N;++i)
        scanf("%d",&A[i]);
    QuickSort(A,0,N-1);
    for(int i=0;i<N;++i)
    {
        printf("%d",A[i]);
        if(i!=N-1)
            printf(" ");
    }
    return 0;   
} 

快速排序的性能

其性能（运行时间）取决于划分是否平衡，而平衡与否又主要依赖于用于划分的元素。如果划分是平衡的，那么快速排序算法性能与归并性能一样。如果划分是不平衡的，那么快速排序的性能会接近于插入排序。

最坏情况划分就是当输入数组是有序时，无论是递增还是递减，快速排序的时间复杂度此时都是$Θ(n^2)$，因为上面的练习已知划分算法Partition的时间复杂度为$Θ(n)$，所以当数组为有序时，QuickSort这个过程一共要去做n次的划分算法Partition，时间复杂度就会变成$Θ(n^2)$了，不过当数组为有序时，插入排序的时间复杂度为$Θ(n)$

最好情况划分

在可能的最平衡的划分中，Partition得到的两个子问题的规模都不大于n/2。这是因为其中一个子问题的规模为￥$\lfloor n/2\rfloor$，而另一个子问题的规模为$\lceil n/2\rceil-1$。在这种情况下，快排整体的性能非常好。此时，算法运行时间的递归式为：$T(n)=2T(n/2)+Θ(n)$，在这个式子中，忽略了一些余项以及减一操作的影响。根据主定理的情况2（树的总代价均匀分布在树的所有层次上），该递归式的解为$T(n)=Θ(nlgn)$。通过在每一层递归中都平衡地划分子数组，我们能得到一个渐进时间上更快地算法。

快速排序的随机化版本

C/C++版本

#include<cstdio>
#include<cstdlib>

void swap(int &a,int &b)
{
    int tmp=a;
    a=b;
    b=tmp;
}

int Partition(int A[],int L,int R)      //划分点选取最后一个
{
    int x=A[R];
    int i=L-1;
    for(int j=L;j<=R-1;j++)
    {
        if(A[j]<=x){
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[R]);
    return i+1;
}

int Randomized_Partition(int A[],int L,int R)
{
    int i=rand()%(R-L+1)+L;
    swap(A[R],A[i]);
    return Partition(A,L,R);
}

void QuickSort(int A[],int Left,int Right)
{
    if(Left<Right)      //数组只剩下一个不需要再划分了 
    {
        int w=Randomized_Partition(A,Left,Right);
        QuickSort(A,Left,w-1);
        QuickSort(A,w+1,Right);
    }
}

int main()
{
    int N;
    scanf("%d",&N); 
    int *A=new int[N];
    for(int i=0;i<N;++i)
        scanf("%d",&A[i]);
    QuickSort(A,0,N-1);
    for(int i=0;i<N;++i)
    {
        printf("%d",A[i]);
        if(i!=N-1)
            printf(" ");
    }
    return 0;   
} 

求第k个小的数

快排，递归一部分，直至找到指定第k个小的数。时间复杂度为$Θ(n)$。

#include<cstdio>
#include<cstdlib>

void swap(int &a,int &b)
{
    int tmp=a;
    a=b;
    b=tmp;
}

int Partition(int A[],int L,int R)      
{
    int x=A[R];
    int i=L-1;
    for(int j=L;j<=R-1;j++)
    {
        if(A[j]<=x){
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[R]);
    return i+1;
}

int Randomized_Partition(int A[],int L,int R)
{
    int i=rand()%(R-L+1)+L;
    swap(A[R],A[i]);
    return Partition(A,L,R);
}

int QuickSort(int A[],int Left,int Right,int k)
{
    if(Left<=Right)     
    {
        int w=Randomized_Partition(A,Left,Right);
        if(w==k-1)
            return A[w];
        else if(w>k-1)
            QuickSort(A,Left,w-1,k);
        else
            QuickSort(A,w+1,Right,k);
    }
}

int main()
{
    int N,k;
    scanf("%d %d",&N,&k); 
    int *A=new int[N];
    for(int i=0;i<N;++i)
        scanf("%d",&A[i]);
    printf("%d",QuickSort(A,0,N-1,k));
    return 0;   
}