算法 #1 排序

本笔记主要关于排序算法。在这一系列笔记中，将使用伪代码；除非数据结构对算法的实现至关重要，否则我们将主要考虑算法本身而非其实现。

下表是常见排序算法的 Cheat Sheet。

$O(n^2)$ 复杂度排序

为了理解排序，我们需要能够使用直观的语言和代码来描述它。

排序问题可以总结为：

输入： $N$ 个无序元素（具有全序关系 <）。
输出： $N$ 个有序元素，从最小到最大。

让我们从 $O(n^2)$ 排序开始。

选择排序 (Selection Sort)

文字描述：

步骤 0：在索引 $[0, n-1]$ 中找到最小值，然后将其与位置 0 的元素交换。
步骤 1：在索引 $[1, n-1]$ 中找到最小值，然后将其与位置 1 的元素交换。
...
步骤 n-1：找到索引 $n-1$ 处的最小值（只剩下一个，因此不需要交换）。

总共执行 $n$ 次交换，每次交换需要检查数组中多达 $n$ 个元素。因此，复杂度为 $O(n^2)$ 。

伪代码描述：

C++for(int i = 0; i < n; i++):
    // 维护每个循环中的最小的数值
    min_index = i
    for(int j = i + 1; j < n; j++):
    // 将 a[i] 与 a[i, length(A)]中最小的元素交换
        if A[j] < A[min_index]
            min_index = j
    swap A[i] and A[min_index]

该算法将第 $i$ 小的元素放入 a[i]。在数组第 $i$ 个位置的左侧是前 $i$ 个最小的元素，它们将不会被再次访问。

时间复杂度：最坏情况 $O(n^2)$ 。

冒泡排序 (Bubble Sort)

从位置 0 开始，比较两个相邻的数字。如果前者比后者大，则交换它们的位置。如果前者较小，则保持不变。
在一轮完整的比较之后，最大的数字将到达最后的位置，就像气泡从水中升到水面一样。
然后重复这个过程，但每次比较的范围都会缩小一个（因为最后一个数字已经排好序了）。
直到不需要交换任何数字，排序完成。

C++for (int i = 0; i < n; i++):  // 控制排序轮数
    for (int j = 0; j < n - i - 1; j++):  // 遍历未排序部分
        if A[j] > A[j + 1]:  // 如果前一个元素比后一个大
            swap A[j] and A[j + 1]  // 交换这两个元素

总共会产生 $n$ 个气泡。每次都会将最大值推向右侧。在最坏的情况下，它将被推送 $O(n)$ 次，因此复杂度为 $O(n^2)$ 。

插入排序 (Insertion Sort)

确保 $[0,0]$ 是有序的（已完成）。
确保 $[0,1]$ 是有序的。
确保 $[0,2]$ 是有序的。
……
确保 $[0, n-1]$ 是有序的。

这就像摸牌一样。

C++for (int i = 1; i < n; i++):
    // 当前抓到的牌是第 i 张牌
    card = A[i]
    j = i - 1
    while j > 0 and A[j] > card:
        // 排序前 i 张牌
        A[j+1] = A[j]
        j = j - 1
    A[j+1] = card

特点：它对初始状态敏感。如果数组已经基本有序，排序速度会快得多。

时间复杂度：平均和最坏情况 $O(n^2)$ ，最好情况 $O(n)$ 。

$O(n\log n)$ 复杂度排序

归并排序 (Merge Sort)

归并排序是一种递归排序算法。文字描述：

首先，对左侧进行排序（递归步骤）
然后，对右侧进行排序（递归步骤）
最后，整合整个数组（merge）

代码描述：

C++mergesort(int[] arr, int L, int R):
	if (L==R) return;
	// 获得中点
	mid = L + ((R-L)>>1);
	// 排序左侧
	mergesort(arr, L, mid);
	// 排序右侧
	mergesort(arr, mid+1, R);
	// 合并步骤
	merge(arr, L, mid, R);

归并排序应用了递归的思想，使用 Divide and Conquer 方法，每次处理一半的排序，最后将它们统一。归并排序在中点处拆分，排序中点前的部分，排序中点后的部分，最后将两个已排序的部分与中点值合并。

在这里，merge 实际上是最重要且最容易出错的部分。

C++merge(int[] arr, int L, int mid, int R):
	// 准备合并用的辅助空间 (其大小为 R-L + 1)
	int[] help = new int[R-L+1];
	// 准备指向左侧第一位的下标和右侧第一位的下标
	int i = 0; p1 = L; p2 = M+1;
	while(p1 <= M && p2 <=R): //左右都不越界
		// 永远先拷贝小的；当左右相等的时候，先复制左侧以保证稳定性
		help[i++] =  arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]; 
	while(p1 <= M): // 这种情况下 p2 先越界了，把 p1 剩下的部分拷贝完
		help[i++] = arr[p1++];
	while(p2 <= R): // 这种情况下 p1 先越界了，把 p2 剩下的部分拷贝完
		help[i++] = arr[p2++];
	for(int i = 0; i < help.length; i++): 
		arr[L+i] = help[i];

但实际上并不难；核心目的只是合并两个已排序的数组。为合并准备的辅助空间长度必须等于两者之和，即 $R - L + 1$ 。然后，使用双指针同时查看两个列表，先拷贝较小的一个。

时间复杂度：平均、最坏和最好情况均为 $O(n \log n)$ 。

快速排序 (Quick Sort)

C++quickSort(A, low, high)
if low < high
    pi = partition(A, low, high)
    quickSort(A, low, pi-1)
    quickSort(A, pi+1, high)
else return

简而言之，快速排序每次选择一个 pivot 值，然后将比 pivot 小的元素扔到其左侧，将比 pivot 大的元素扔到其右侧，然后递归地对两侧进行快速排序。

平均情况： $O(n \log n)$

最好情况： $O(n \log n)$

最坏情况： $O(n^2)$ —— 当数组已经排序或所有元素都相等时。

交换操作 (Swap Operation)

在这里，我们专门介绍基于 XOR 操作 (^) 的交换。我们可以使用以下代码交换数据。

C++int a, b; // 假设 a 和 b 现在都已经初始化并且有值
a = a ^ b;
b = a ^ b;
a = a ^ b; // 此时 a 和 b 已经完成数据的交换

XOR 操作是一种位运算。其性质是如果两个位相等，则 XOR 结果为 0；如果不同，则为 1，即：

1 ^ 1 = 0, 0 ^ 0 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1;

因此，它满足以下性质：

0 ^ n = n.
n ^ n = 0. => a ^ b ^ a = a ^ a ^ b = 0 ^ b = b.
a ^ b = b ^ a.
a ^ (b ^ c) = (a ^ b) ^ c.

读者可以自行验证上述三行代码的效果。

参考资料：

Introduction to Algorithm, 3rd Edition

O(n2)O(n^2)O(n2) 复杂度排序