Exchange Sorts

交换类排序

交换类排序的共同点是：根据两个元素关键字的比较结果，交换它们在序列中的位置。

主要讨论两种交换类排序：

  • 冒泡排序：只比较相邻元素，若相邻逆序则交换。
  • 快速排序：通过一次划分把枢轴放到最终位置，再递归处理左右子表。

冒泡排序

冒泡排序从后往前或从前往后两两比较相邻元素。如果相邻元素逆序，就交换它们。一趟冒泡结束后，会有一个元素到达最终位置。

下面采用“从后往前冒泡”的写法：每一趟把当前无序区中最小的元素冒到最前面。

如果一次处理无交换发生，则说明已经有序，提前停止算法。

冒泡排序的 C 写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Sorts an integer array in nondecreasing order using bubble sort.
 *
 * Args:
 *   a: Array to sort in place.
 *   n: Number of elements in the array.
 *
 * Notes:
 *   This version scans from right to left. After pass i, a[0..i] contains
 *   the i+1 smallest elements in final order.
 */
void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;  // 本趟是否发生交换，用于提前结束

        for (int j = n - 1; j > i; j--) {
            if (a[j - 1] > a[j]) {
                int temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
                swapped = 1;
            }
        }

        if (!swapped) {
            break;        // 本趟无交换，说明整体已经有序
        }
    }
}

这段代码只在 a[j - 1] > a[j] 时交换。若两个元素相等，不交换，所以冒泡排序稳定。

冒泡排序的效率

情况 比较次数 交换次数 时间复杂度
最好，原本有序 $n-1$ $0$ $O(n)$
最坏，原本逆序 $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{2}$ $O(n^2)$
平均 $O(n^2)$ $O(n^2)$ $O(n^2)$

空间复杂度为 $O(1)$。

每次交换通常需要 3 次移动：

1
2
3
temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;

冒泡排序与链表

冒泡排序可以用于链表。

如果在链表中从前往后冒泡，每一趟可以把较大的元素冒到链尾。链表结点之间不能像数组那样按下标直接访问，但冒泡只需要顺着 next 比较相邻结点，因此可以实现。

不过链表冒泡仍然要多趟相邻比较，时间复杂度仍是 $O(n^2)$。

快速排序

快速排序的核心是一次划分：

  1. 在待排序区间中选一个元素作为枢轴 pivot，这里采用首元素作为枢轴。
  2. 通过一趟划分，使枢轴左侧元素都小于 pivot，右侧元素都大于等于 pivot。
  3. 枢轴被放到最终位置。
  4. 递归处理左右两个子表。

一次划分的循环不变量

代码实现详见 循环不变量双指针写法 。

采用半开区间 [lo, hi)。取 A[lo] 为枢轴，初始化：

1
2
3
pivot = A[lo]
i = lo
j = hi - 1

每轮循环开始时，数组被看成四段：

$$
{lo},\quad [lo+1,i],\quad [i+1,j],\quad [j+1,hi)
$$

四段语义分别是：

  • A[lo] 保存枢轴。
  • A[lo+1..i] < pivot，这是已经确认的小于区。
  • A[i+1..j] 还没有确认。
  • A[j+1..hi-1] >= pivot，这是已经确认的大于等于区。

这就是划分过程的循环不变量。算法每一步只是扩大左边的小于区和右边的大于等于区，缩小中间的未知区。

一次划分后：

  1. 枢轴已经在最终位置。
  2. 枢轴左侧所有元素都小于枢轴。
  3. 枢轴右侧所有元素都大于等于枢轴。
  4. 左右两侧内部不要求有序。
Warning

一次划分 $\ne$ 一趟快速排序。一次划分只确定一个枢轴的最终位置；若题目把“对所有尚未确定最终位置的区间都处理一遍”称为一趟排序，那么一趟排序可能确定多个枢轴位置。

### 快速排序的递归层数

快速排序的时间和空间都与递归层数有关。

每一层所有子表的划分总工作量不超过 $O(n)$，所以：

$$
\text{时间复杂度}=O(n \times \text{递归层数})
$$

递归工作栈的深度就是递归层数，所以：

$$
\text{空间复杂度}=O(\text{递归层数})
$$

若把快速排序的递归过程看成一棵二叉树：

  • 最好情况：每次枢轴都把序列均匀分成两半，递归树高度约为 $\lfloor \log_2 n \rfloor + 1$。
  • 最坏情况：每次枢轴都落在最边上，递归树退化为一条链，高度为 $n$。

因此：

情况 递归层数 时间复杂度 空间复杂度
最好 $O(\log_2 n)$ $O(n\log_2 n)$ $O(\log_2 n)$
平均 $O(\log_2 n)$ $O(n\log_2 n)$ $O(\log_2 n)$
最坏 $O(n)$ $O(n^2)$ $O(n)$

若初始序列已经有序或逆序，并且每次都取首元素为枢轴，那么每次划分都极不均匀，快速排序性能最差。

最好情况下关键字比较次数

最好情况下，每次枢轴都把当前序列尽量均分。

一次划分长度为 $n$ 的表时，枢轴要与其他元素比较，数量级为 $n-1$ 次。因此比较次数$C(n)$可以按递推式理解：

$$
C(0)=C(1)=0
$$

$$
C(n)=C(\lfloor \frac{n-1}{2}\rfloor)+C(\lceil \frac{n-1}{2}\rceil)+(n-1)
$$

数量级为：

$$
C(n)=O(n\log_2 n)
$$

Example

$n=7$ 且每次正好均分：

1
2
3
第一层：长度 7，比较 6 次
第二层：两个长度 3 的子表，各比较 2 次
第三层：四个长度 1 的子表，不再划分
> 所以： > > $$ C(7)=6+2+2=10 $$

稳定性

快速排序不稳定。

一个简单反例：

1
2a 2b 1

若取 2a 为枢轴，一次划分后可能变成：

1
1 2b 2a

两个关键字都为 2 的记录相对次序从 2a, 2b 变成 2b, 2a，所以快速排序不稳定。

小结

算法 最好 平均 最坏 空间 稳定性
冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
快速排序 $O(n\log_2 n)$ $O(n\log_2 n)$ $O(n^2)$ 平均 $O(\log_2 n)$，最坏 $O(n)$ 不稳定