8.2 交换排序：冒泡与快速排序

冒泡排序的过程与提前结束条件，快速排序的划分（Partition）过程、递归深度、最好与最坏情况分析。

所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

冒泡排序

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

1void BubbleSort(int A[], int n) {
2    for (int i = 0; i < n - 1; i++) {
3        bool flag = false;               // 本趟是否发生交换
4        for (int j = n - 1; j > i; j--)  // 从后往前一趟冒泡
5            if (A[j-1] > A[j]) {         // 若为逆序
6                swap(A[j-1], A[j]);      // 交换
7                flag = true;
8            }
9        if (flag == false)
10            return;                      // 本趟无交换，已经有序
11    }
12}

性能分析：

• 空间效率：仅使用了常数个辅助单元，空间复杂度为 $O(1)$。
• 时间效率：当初始序列有序时，显然第一趟冒泡后 flag 依然为 false（本趟没有元素交换），从而直接跳出循环，比较次数为 $n - 1$，移动次数为 0，从而最好情况下的时间复杂度为 $O(n)$；当初始序列为逆序时，需要进行 $n - 1$ 趟排序，第 $i$ 趟排序要进行 $n - i$ 次关键字的比较，而且每次比较后都必须移动元素 3 次来交换元素位置：

从而，最坏情况下的时间复杂度为 $O(n^2)$，平均时间复杂度为 $O(n^2)$。

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

快速排序

快速排序的基本思想是基于分治法的：在待排序表 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) 上，这个过程称为一次划分。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

在上面的动画中切换到”快速排序”。注意观察”挖坑填数”的过程：

1. 取出枢轴，low 处留下一个”坑”；
2. high 从右往左找比枢轴小的元素，填到左边的坑里，high 处变成新坑；
3. low 从左往右找比枢轴大的元素，填到右边的坑里，low 处变成新坑；
4. 重复 2、3，直到 low == high，把枢轴放入最后的坑——这就是它的最终位置。

性能分析：

• 空间效率：由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大深度一致。最好情况下为 $O(\log_2 n)$；最坏情况下，因为要进行 $n - 1$ 次递归调用，所以栈的深度为 $O(n)$；平均情况下，栈的深度为 $O(\log_2 n)$。
• 时间效率：快速排序的运行时间与划分是否对称有关，快速排序的最坏情况发生在两个区域分别包含 $n - 1$ 个元素和 0 个元素时，这种最大限度的不对称性若发生在每层递归上，即对应于初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为 $O(n^2)$。在最理想的状态下，即 Partition() 能做到最平衡的划分，得到的两个子问题的大小都不可能大于 $n/2$，在这种情况下，快速排序的运行速度将大大提升，此时，时间复杂度为 $O(n\log_2 n)$。好在快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况下的运行时间。快速排序是所有内部排序算法中平均性能最优的排序算法。
• 稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序算法。例如，表 $L = \{3, 2, \underline{2}\}$，经过一趟排序后 $L = \{\underline{2}, 2, 3\}$。

int setPartition(int a[], int n) {
    int pivotkey, low = 0, low0 = 0, high = n - 1, high0 = n - 1;
    int flag = 1, k = n / 2, i, s1 = 0, s2 = 0;
    while (flag) {
        pivotkey = a[low];                       // 选择枢轴
        while (low < high) {                     // 基于枢轴对数据进行划分
            while (low < high && a[high] >= pivotkey) --high;
            if (low != high) a[low] = a[high];
            while (low < high && a[low] <= pivotkey) ++low;
            if (low != high) a[high] = a[low];
        }
        a[low] = pivotkey;
        if (low == k - 1) flag = 0;              // 枢轴是第 n/2 小的元素，划分成功
        else if (low < k - 1) { low0 = ++low; high = high0; }   // 继续划分右部
        else { high0 = --high; low = low0; }                     // 继续划分左部
    }
    for (i = 0; i < k; i++) s1 += a[i];
    for (i = k; i < n; i++) s2 += a[i];
    return s2 - s1;
}

即时练习