前言

【算法导论描述】:快速排序在输入为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;   
} 
Last modification:October 6, 2023
兴趣使然