数据结构复习指导之交换排序（冒泡排序，快速排序）

交换排序

复习提示

1.冒泡排序

1.1基本思想

1.2算法代码

1.3性能分析

2.快速排序

2.1基本思想

2.2算法代码

2.3性能分析

交换排序

复习提示

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。
基于交换的排序算法很多，本书主要介绍冒泡排序和快速排序，

其中冒泡排序算法比较简单，一般很少直接考查，通常会重点考查快速排序算法的相关内容。

1.冒泡排序

1.1基本思想

冒泡排序的基本思想是：

从后往前(或从前往后)两两比较相邻元素的值，若为逆序(即A[i-1]>A[i])，则交换它们，直到序列比较完。
我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置(或将最大的元素交换到待排序列的最后一个位置)，
关键字最小的元素如气泡一般逐渐往上“漂浮”至“水面”(或关键字最大的元素如石头一般下沉至水底)。
下一趟冒泡时,前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素(或最大元素)放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。

图 8.3所示为冒泡排序的过程，

第一趟冒泡时:

$27<\overline{49}$ ，不交换；
13<27，不交换；
76>13，交换；
97>13，交换；
65>13，交换；
38>13，交换；
49>13，交换。

通过第一趟冒泡后，最小元素已交换到第一个位置，也是它的最终位置。

第二趟冒泡时对剩余子序列采用同样方法进行排序，如此重复，到第五趟结束后没有发生交换，说明表已有序，冒泡排序结束。

1.2算法代码

冒泡排序算法的代码如下:

void BubbleSort(ElemType A[],int n){
    for(int i=0;i<n-1;i++){
        bool flag=false;           //表示本趟冒泡是否发生交换的标志
        for(int j=n-1;j>i;j--)     //一趟冒泡过程
            if(A[j-1]>A[j]){       //若为逆序
                swap(A[j-1],A[j]); //使用封装的 swap 函数交换
                flag=true;
            }
        if(flag==false)
            return;                //本趟遍历后没有发生交换，说明表已经有序
    }
}

1.3性能分析

冒泡排序的性能分析如下：

空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。

时间效率：当初始序列有序时，显然第一趟冒泡后 flag 依然为 false(本趟没有元素交换)，从而直接跳出循环，比较次数为n-1，移动次数为0，

从而最好情况下的时间复杂度为 O(n)；
当初始序列为逆序时，需要进行n-1趟排序，第 i 趟排序要进行n-i次关键字的比较，而且每次比较后都必须移动元素3次来交换元素位置。
这种情况下，
比较次数= $\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}$
移动次数= $\sum_{i=1}^{n-1}3(n-i)=\frac{3n(n-1)}{2}$
从而，最坏情况下的时间复杂度为 O(n²)，平均时间复杂度为 O(n²)。

稳定性：由于 i>j 且 A[i]=A[j] 时，不会发生交换，因此冒泡排序是一种稳定的排序算法。

适用性：冒泡排序适用于顺序存储和链式存储的线性表。

注意：冒泡排序中所产生的有序子序列一定是全局有序的(不同于直接插入排序)，也就是说，有序子序列中的所有元素的关键字一定小于(或大于)无序子序列中所有元素的关键字，这样每趟排序都会将一个元素放置到其最终的位置上。

2.快速排序

2.1基本思想

快速排序(以下有时简称快排)的基本思想是基于分治法的：

在待排序表 L[1..n] 中任取一个元素 pivot 作为枢轴(或称基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分 L[1..k-1] 和 L[k+1..n]，使得L[1..k-1]中的所有元素小于pivot，L[k+1..n]中的所有元素大于或等于 pivot，则 pivot 放在了其最终位置L(k)上，这个过程称为一次划分。
然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或为空为止，即所有元素放在了其最终位置上。

一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍，附设两个指针i和 j，初值分别为 low 和 high，取第一个元素 49 为枢轴赋值到变量 pivot。

【命题追踪——快速排序的中间过程的分析(2014、2019、2023)】

此时，指针 i(==j) 之前的元素均小于 49，指针 i 之后的元素均大于或等于 49，将 49 放在 i 所指位置即其最终位置，经过第一趟排序后，将原序列分割成了前后两个子序列。

按照同样的方法对各子序列进行快速排序，若待排序列中只有一个元素，显然已有序。

用二叉树的形式描述这个举例的递归调用过程，如图 8.4所示。

假设划分算法已知，记为Partition()，返回的是上述的k，则 L(k) 已放在其最终位置。

2.2算法代码

因此可以先对表进行划分，然后对两个子表递归地调用快速排序算法进行排序。代码如下:

void QuickSort(ElemType A[],int low,int high){
    if(low<high){                              //递归跳出的条件
    //Partition()就是划分操作，将表A[low…high]划分为满足上述条件的两个子表
        int pivotpos=Partition(A,low,high);    //划分
        Quicksort(A,low,pivotpos-1);           //依次对两个子表进行递归排序
        Quicksort(A,pivotpos+l,high);
    }
}

【命题追踪——(算法题)快速排序中划分操作的应用(2016)】

快速排序算法的性能主要取决于划分操作的好坏。考研所考查的快速排序的划分操作通常总
以表中第一个元素作为枢轴来对表进行划分，则将表中比枢轴大的元素向右移动，将比枢轴小的
元素向左移动，使得一趟 partition()操作后，表中的元素被枢轴一分为二。代码如下:

int Partition(ElemType A[],int low,int high){ //一趟划分
    ElemType pivot=A[low]; //将当前表中第一个元素设为枢轴，对表进行划分
    while(low<high){     //循环跳出条件
        while(low<high&&A[high]>=pivot)--high;
        A[low]=A[high];  //将比枢轴小的元素移动到左端
        while(low<high && A[low]<=pivot) ++low;
        A[high]=A[low];  //将比枢轴大的元素移动到右端
    }  
    A[low]=pivot;        //枢轴元素存放到最终位置
    return low;          //返回存放枢轴的最终位置
}

2.3性能分析

快速排序算法的性能分析如下：
【命题追踪——快速排序中递归次数的影响因素分析(2010)】

空间效率：由于快速排序是递归的，因此需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大层数一致。
最好情况下为 O(log₂n)；
最坏情况下，要进行n-1次递归调用，因此栈的深度为 O(n)；
平均情况下，栈的深度为 O(log₂n)。

时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含n-1个元素和0个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为 O(n²)。

有很多方法可以提高算法的效率：一种方法是尽量选取一个可以将数据中分（对称平分）的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素；或者随机地从当前表中选取枢轴元素，这样做可使得最坏情况在实际排序中几乎不会发生。

在最理想的状态下，即 Partition()能做到最平衡的划分，得到的两个子问题的大小都不可能大于 n/2，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为 O(nlog₂n)。
好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。
快速排序是所有内部排序算法中平均性能最优的排序算法。

稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序算法。
例如，表L=(3,2,2)，经过一趟排序后L={2,2,3}，最终排序序列也是L={2,2,3}，显然，2与2的相对次序已发生了变化。

适用性：快速排序仅适用于顺序存储的线性表。