21天学习挑战赛-剖析快速排序

2022-08-15
2


活动地址:CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸,早一天就多一份人生的精彩;迟一天就多一天平庸的困扰。各位小伙伴,如果您:
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持,想组团高效学习…
想写博客但无从下手,急需写作干货注入能量…
热爱写作,愿意让自己成为更好的人…

快速排序

快速排序(Quick Sort 是对起泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

1. 排序过程

假设待排序的序列为 { L . r [ s ] , L . r [ s + 1 ] , ⋯   , L . r [ t ] } \{\mathrm{L}.\mathrm{r}[\mathrm{s}], \mathrm{L}.\mathrm{r}[\mathrm{s}+1], \cdots, \mathrm{L} . \mathrm{r}[\mathrm{t}]\} {L.r[s],L.r[s+1],,L.r[t]}

  1. 首先任意选取一个记录(通常可选第一个记录 L . r [ s ] L.r[s] L.r[s])作为枢轴(或支点)(pivot)
  2. 然后按下述原则重新排列其余记录:将所有关键字较它小的记录都安置在它的位置之前,将所有关键字较它大的记录都安置在它的位置之后。

由此可以该“枢轴”记录最后所落的位置 i 作分界线,将序列 { L . r [ s ] , ⋯   , L . r [ t ] } \{L.r[s],\cdots,L.r[t]\} {L.r[s],,L.r[t]} 分割成两个子序列 { L . r [ s ] , L . r [ s + 1 ] , ⋯   , L . r [ i − 1 ] } \{L.r[s], L.r[s + 1], \cdots, L.r[i - 1]\} {L.r[s],L.r[s+1],,L.r[i1]} { L . r [ i + 1 ] , L . r [ i + 2 ] , ⋯   , L . r [ t ] } \{L.r[i + 1], L.r[i + 2], \cdots, L.r[t] \} {L.r[i+1],L.r[i+2],,L.r[t]}。这个过程称做一趟快速排序(或一次划分)。

2. 非递归算法
算法 10.6(a)
int Partition (SqList & L, int low, int high){

    //交换顺序表 L 中子表 L.r[1ow..high] 的记录,使枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大(小)于它。
    pivotkey = L.r[low].key;                            //用子表的第一个记录作枢轴记录

    while(low < high){                                  //从表的两端交替地向中间扫描
        
        while(low < high && L.r[high].key >= pivotkey)  //跳出循环的条件之一就是找到了 high,使得 L.r[high].key < pivotkey
            -- high;
            
        L.r[low] <--> L.r[high];                        //将比枢轴记录小的记录交换到低端 

        while(low < high && L.r[low].key <= pivotkey) 
            ++ low; 
        
        L.r[low] <--> L.r[high];                        //将比枢轴记录大的记录交换到高端
    }
    
    return low;                                         //返回枢轴所在位置

}//Partition

具体实现上述算法时,每交换一对记录需进行 3 次记录移动(赋值)的操作。而实际上,在排序过程中对枢轴记录的赋值是多余的,因为只有在一趟排序结束时,即 l o w = = h i g h low == high low==high 的位置才是枢轴记录的最后位置。由此可改写上述算法,先将枢轴记录暂存在 r [ 0 ] r [0] r[0] 的位置上,排序过程中只作 r [ l o w ] r[low] r[low] r [ h i g h ] r[high] r[high] 的单向移动,直至一趟排序结束后再将枢轴记录移至正确位置上。如算法 10.6(b)所示。

算法 10.6(b)
int Partition (SqList & L, int low, int high){

    //交换顺序表中子表 r[low..high] 的记录,枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大(小)于它。
    L.r[0] = L.r[low];                                  //用子表的第一个记录作枢轴记录 
    pivotkey = L.r[low].key;                            //枢轴记录关键字 
    
    while (low < high){                                 //从表的两端交替地向中间扫描

        while (low < high && L.r[high].key >= pivotkey) 
            --high;

        L.r[low] = L.r[high];                           //将比枢轴记录小的记录移到低端

        while (low < high && L.r[low]. Key <= pivotkey) 
            ++ low;

        L.r[high] = L.r[low];                           //将比枢轴记录大的记录移到高端
    }

    L.r[low] = L.r[0];                                  //枢轴记录到位

    return low; //返回枢轴位置 

}// Partition
3. 递归算法

递归形式的快速排序算法如算法 10.7 和算法 10.8 所示。

算法 10.7
void QSort (Sqlist & L, int low, int high){

    //对顺序表 L 中的子序列 L.r[low, high] 作快速排序
    if (low < high){                                    //长度大于 1
        pivotloc = Partition(L, low, high);             //将 L.r[low .. high] ー分为二

    QSort(L, low, pivotloc - 1);                        //对低子表递归排序,pivotloc 是枢轴位置
    QSort(L, pivotloc + 1, high);                       //对高子表递归排序

}// Sort
算法 10.8
void QuickSort (Sqlist & L){

    //对顺序表 L 作快速排序。
    QSort (L, 1, L.length);
    
}//QuickSort
4. 复杂度分析

快速排序的平均时间为 T a v g ( n ) = k n ln ⁡ n T_{avg}(n) = kn \ln n Tavg(n)=knlnn,其中 n n n 为待排序序列中记录的个数, k k k 为某个常数,经验证明,在所有同数量级的此类(先进的)排序方法中,快速排序的常数因子 k k k 最小。因此,就平均时间而言,快速排序是目前被认为是最好的一种内部排序方法。

快排算法的平均时间性能

下面我们来分析快速排序的平均时间性能。

假设 T ( n ) T(n) T(n) 为对 n 个记录 L . r [ 1.. n ] L.r[1..n] L.r[1..n] 进行快速排序所需时间,则由算法 QuickSort 可见,

T ( n ) = T pass ( n ) + T ( k − 1 ) + T ( n − k ) \qquad T(n) = T_{\text {pass}}(n) + T(k - 1) + T(n - k) T(n)=Tpass(n)+T(k1)+T(nk)

其中 T pass  ( n ) T_{\text {pass }}(n) Tpass (n) 为对 n 个记录进行一趙快速排序 P a r t i t i o n ( L , 1 , n ) Partition(L,1,n) Partition(L,1,n) 所需时间,从算法 10.7 可见,它和记录数 n n n 成正比,可以 c n cn cn 表示之( c c c 为某个常数); T ( k − 1 ) T(k - 1) T(k1) T ( n − k ) T(n - k) T(nk) 分别为对 L . r [ 1.. K − 1 ] L.r[1 .. K - 1] L.r[1..K1] L . r [ k + 1.. n ] L.r [k + 1 .. n] L.r[k+1..n] 中记录进行快速排序 Q S o r t ( L , 1 , k − 1 ) QSort(L, 1, k - 1) QSort(L,1,k1) Q S o r t ( L , k + 1 , n ) QSort(L, k + 1, n) QSort(L,k+1,n) 所需时间。假设待排序列中的记录是随机排列的,则在一趟排序之后, k k k 1 1 1 n n n 之间任何一值的概率相同,快速排序所需时间的平均值则为

T a v g ( n ) = c n + 1 n ∑ k = 1 n [ T a v g ( k − 1 ) + T a v g ( n − k ) ] \qquad\begin{aligned} T_{avg}(n) = cn + \frac{1}{n} \sum_{k=1}^{n}\left[T_{a v g}(k-1)+T_{a v g}(n-k)\right] \end{aligned} Tavg(n)=cn+n1k=1n[Tavg(k1)+Tavg(nk)]
     = c n + 2 n ∑ i = 0 n − 1 T a v g ( i ) ( 10 − 8 ) \qquad\quad\;\;\qquad\begin{aligned} = cn + \frac{2}{n} \sum_{i=0}^{n-1} T_{avg}(i)\end{aligned} \qquad\qquad\qquad (10 - 8) =cn+n2i=0n1Tavg(i)(108)

假定 T avg  ( 1 ) ⩽ b T_{\text {avg }}(1) \leqslant b Tavg (1)b ( b b b 为某个常量),类同式 ( 9 − 19 ) (9 - 19) (919) 的推导,由式 ( 10 − 8 ) (10 - 8) (108) 可推出

T avg  ( n ) = n + 1 n T avg  ( n − 1 ) + 2 n − 1 n c < n + 1 2 T avg  ( 1 ) + 2 ( n + 1 ) ( 1 2 + 1 3 + ⋯ + 1 n + 1 ) c < ( b 2 + 2 c ) ( n + 1 ) ln ⁡ ( n + 1 ) n ⩾ 2 ( 10 − 9 ) \qquad\begin{aligned} T_{\text {avg }}(n) &=\frac{n+1}{n} T_{\text {avg }}(n-1)+\frac{2 n-1}{n} c \\ &<\frac{n+1}{2} T_{\text {avg }}(1)+2(n+1)\left(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n+1}\right) c \\ &<\left(\frac{b}{2}+2 c\right)(n+1) \ln (n+1) \quad n \geqslant 2 \end{aligned} \qquad\qquad\qquad (10 - 9) Tavg (n)=nn+1Tavg (n1)+n2n1c<2n+1Tavg (1)+2(n+1)(21+31++n+11)c<(2b+2c)(n+1)ln(n+1)n2(109)

通常,快速排序被认为是,在所有同数量级 ( O ( n l o g n ) (O(n logn) (O(nlogn) 的排序方法中,其平均性能最好。但是,若初始记录序列按关键字有序或基本有序时,快速排序将蜕化为起泡排序,其时间复杂度为 O ( n 2 ) O(n^2) O(n2)

快排算法的改进 - 枢轴的选取

为改进之,通常依“三者取中”的法则来选取枢轴记录,即比较 L . r [ s ] . k e y 、 L . r [ t ] . k e y L.r[s].key、L.r[t].key L.r[s].keyL.r[t].key L . r [ ⌊ s + t 2 ⌋ ] . k e y L.r \begin{aligned}\left[\left\lfloor\frac{s+t}{2}\right\rfloor\right].key \end{aligned} L.r[2s+t].key,取三者中其关键字取中值的记录为枢轴,只要将该记录和 L . r [ s ] L.r[s] L.r[s] 互换,算法 10.6 ( b ) 10.6(b) 10.6(b) 不变。经验证明,采用三者取中的规则可大大改善快速排序在最坏情况下的性能。然而,即使如此,也不能使快速排序在待排记录序列已按关键字有序的情况下达到 O ( n ) O(n) O(n) 的时间复杂度。

为此,可如下所述修改“一次划分”算法:在指针 h i g h high high 减 1 和 l o w low low 增 1 的同时进行“起泡”操作,即在相邻两个记录处于“逆序”时进行互换,同时在算法中附设两个布尔型变量分别指示指针 l o w low low h i g h high high 在从两端向中间的移动过程中是否进行过交换记录的操作,若指针 l o w low low 在从低端向中间的移动过程中没有进行交换记录的操作,则不再需要对低端子表进行排序;类似地,若指针 h i g h high high 在从高端向中间的移动过程中没有进行交换记录的操作,则不再需要对高端子表进行排序。显然,如此“划分”将进一步改善快速排序的平均性能。

5. 总结

由以上讨论可知,从时间上看,快速排序的平均性能优于前面讨论过的各种排序方法,从空间上看,前面讨论的各种方法,除 2-路插入排序之外,都只需要一个记录的附加空间即可,但快速排序需一个栈空间来实现递归。若每一趟排序都将记录序列均匀地分割成长度相接近的两个子序列,则栈的最大深度为 ⌊ log ⁡ 2 n ⌋ + 1 \left\lfloor\log _{2} n\right\rfloor+1 log2n+1(包括最外层参量进栈),但是,若每趟排序之后,枢轴位置均偏向子序列的一端,则为最坏情况,栈的最大深度为 n n n。如果改写算法 10.7, 在一趟排序之后比较分割所得两部分的长度,且先对长度短的子序列中的记录进行快速排序,则栈的最大深度可降为 O ( l o g n ) O(logn) O(logn)

相关信息

    评论