交换排序¶

交换排序根据两个元素关键字的比较结果, 决定要不要对调它们的位置. 408 里这一类主要是冒泡排序和快速排序.

冒泡排序¶

冒泡排序 | Hello 算法

冒泡排序（Bubble Sort）反复比较相邻元素: 若逆序 (左 > 右) 就交换. 一趟从左扫到右之后, 当前未排序区间里最大的那个会沉到右端, 像气泡升到水面 (或石头沉底). 下一趟不再碰已经就位的后缀, 最多 \(n-1\) 趟.

以 \(\{5, 2, 4, 1, 3\}\) 为例, 竖线右侧是已经就位的后缀:

5  2  4  1  3 |
2  4  1  3 | 5      第一趟: 最大的 5 沉底
2  1  3 | 4  5      第二趟
1  2 | 3  4  5      第三趟
1 | 2  3  4  5      第四趟无交换, 可提前停

算法实现¶

void bubble_sort(int a[], int n) {
    int i, j, tmp;
    for (i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped)            /* 本趟没有交换, 已经有序 */
            return;
    }
}

将扫描过程改成从后往前扫, 每趟把最小的沉到未排序区间左端, 道理相同.

算法分析¶

• 无 swapped(用于记录本趟遍历是否发生交换) 时比较次数固定 \(\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}\), \(O(n^2)\)

• 加 swapped 后最佳情况(已正序)一趟无交换就停, 时间复杂度 \(O(n)\); 最坏情况(逆序) / 平均情况仍 \(O(n^2)\)

• 空间复杂度 \(O(1)\), 原地算法

• 稳定: 只在 > 时交换, 相等不插队. 改成 >= 就不稳定¹.

• 顺序表、链表都能做, 链表上交换节点比交换值麻烦, 一般不优先用冒泡

每趟结束后, 至少有一个元素到达最终位置. 这点和简单选择一样, 但冒泡靠相邻交换逐步挤过去, 选择是直接找出最值再换.

快速排序¶

快速排序 | Hello 算法

快速排序（Quick Sort）和归并排序一样都是分治, 都把大区间拆成两半再递归. 差别在力气花在哪一步.

分治可以看成三步: 先切开, 再分别排序, 最后把两半的结果合并回去.

• 归并: 切开最省事 (按下标对半, \(O(1)\)). 费时间的是合并: 两个有序段要 \(\Theta(n)\) 做 merge, 还得另开数组

• 快排: 切开最费事, 就是下面的划分(partition), 也要扫 \(\Theta(n)\). 划完后枢轴已经在最终位置, 左边全小、右边全大, 两半互不干扰, 不用再合并, 递归返回即可

所以归并的难点在「合并」, 快排的难点在「划分」. 这也是快排能原地做、归并通常要 \(\Theta(n)\) 辅助空间的原因.

快排的工作流程如下:

1. 在 \(a[\textit{start}..end]\) 里选一个枢轴(pivot, 408中默认取当前区间最左)

2. 划分(partition): 把比它小的都挪到左边, 大的都挪到右边, 枢轴落到最终位置 \(mid\)

3. 对 \(a[\textit{start}..mid-1]\) 和 \(a[mid+1..end]\) 递归. Base Case 是区间长度 \(\leqslant 1\)

划分¶

408中常用「挖坑填数」: 先把枢轴掏出来, 右指针找小的填到左边的坑, 左指针找大的填到右边的坑, 相遇处把枢轴放回去.

int partition(int a[], int low, int high) {
    int 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;
}

void quick_sort(int a[], int low, int high) {
    if (low < high) {
        int mid = partition(a, low, high);
        quick_sort(a, low, mid - 1);
        quick_sort(a, mid + 1, high);
    }
}

和归并不同: 快排是先划分、再递归 (先序), 不是后序. low >= high 时区间长度 \(\leqslant 1\), 直接返回.

以 \(\{49, 38, 65, 97, 76, 13, 27, 49\}\) 为例. 第一趟划分 (枢轴 \(49\)):

49  38  65  97  76  13  27  49     掏出 49, 右找 27 填到坑
27  38  65  97  76  13  65  49     左找 65 填到右边
27  38  13  97  76  97  65  49     右找 13, 左找 97
27  38  13  49  76  97  65  49     两指针相遇, 放入 49
            ^
           mid = 3

左段 \(\{27, 38, 13\}\) 都 \(\leqslant 49\), 右段 \(\{76, 97, 65, 49\}\) 都 \(\geqslant 49\). 之后只递归两段, 不再跨过这个 \(49\).

完整调用树 (箭头右侧是该次 partition 返回后的整表; 已就位的枢轴用 | | 标出):

qs(0, 7)                            [49, 38, 65, 97, 76, 13, 27, 49]
└─ partition(0, 7) → mid=3          [27, 38, 13 |49| 76, 97, 65, 49]
   ├─ qs(0, 2)
   │  └─ partition(0, 2) → mid=1    [13 |27| 38 |49| 76, 97, 65, 49]
   │     ├─ qs(0, 0)                [13]                 base
   │     └─ qs(2, 2)                [38]                 base
   └─ qs(4, 7)
      └─ partition(4, 7) → mid=6   [13, 27, 38 |49| 49, 65 |76| 97]
         ├─ qs(4, 5)
         │  └─ partition(4, 5) → mid=4
         │     ├─ qs(4, 3)          空区间              base
         │     └─ qs(5, 5)          [65]               base
         └─ qs(7, 7)                [97]                 base

每次 partition 只改当前区间, 已就位的枢轴不再动. 按时间顺序看整表:

初始                    49  38  65  97  76  13  27  49
partition(0, 7)         27  38  13 |49| 76  97  65  49
partition(0, 2)         13 |27| 38 |49| 76  97  65  49
partition(4, 7)         13  27  38 |49| 49  65 |76| 97
partition(4, 5)         13  27  38 |49| 49 |65| 76  97

qs(4, 5) 以 \(49\) 为枢轴时, 右侧 \(65\) 不小于它, 划分得到空左段 qs(4, 3) 和单元素右段. 这就是「一边空」的缩影, 有序数组上若总取最左当枢轴, 每一趟都会这样, 递归退化成链.

时间复杂度¶

一次 partition 扫完当前区间, \(\Theta(n)\). 总时间取决于划分是否均匀:

• 最好: 每次都劈成两半, \(T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)\), 递归树高 \(\log n\), 每层 \(\Theta(n)\)

• 最坏: 已正序或逆序, 取最左当枢轴会得到 \(0\) 和 \(n-1\), \(T(n)=T(n-1)+\Theta(n)=\Theta(n^2)\), 退化成和冒泡同阶. 递归树退化成一条链

• 平均: 枢轴秩均匀时仍是 \(\Theta(n\log n)\). 快排是内部排序里平均最快的算法之一, 常数比归并小

空间与稳定性¶

• 递归栈: 最好 / 平均 \(O(\log n)\), 最坏 \(O(n)\)

• 划分本身 \(O(1)\) 额外变量, 整体仍算原地 (不计栈的话教材常写 \(O(\log n)\) 平均)

• 不稳定. 划分会把右侧较小的直接盖到左边, 相等关键字可能换序. 例如 \(\{5_a, 3, 5_b\}\) 以 \(5_a\) 为枢轴, 一趟后可变成 \(\{3, 5_b, 5_a\}\)

只适合顺序表: 划分要两端跳跃访问. 链表上也能写, 但失去快排的常数优势.

避免最坏¶

• 随机枢轴或三数取中 (头、中、尾的中位数), 降低一直拿到最值的概率

• 区间很短时改直接插入

• 先递归较短的一侧, 另一侧改循环 (尾递归), 把最坏栈深往 \(O(\log n)\) 按

全相等的数组若用 <= / >= 扫指针, 仍可能一边空. 三路划分 (小于 / 等于 / 大于) 可一次把等于枢轴的都就位.

只要第 \(k\) 小、不必整表有序时, 同一套 partition 只递归一侧, 就是快速选择.

两种交换排序对照¶

和归并相比, 二者平均都是 \(\Theta(n\log n)\), 归并最坏也稳在这, 且稳定、要 \(\Theta(n)\) 辅助数组; 快排是原地算法、常数小, 但不稳定、会退化.