这篇笔记主要是关于排序的算法。在这个系列的笔记全部都会采用伪代码的形式；除非在一些时候数据结构对于一个算法的实现非常重要，否则大部分时候我们将主要考虑算法本身，而不是算法的实现。

下表为常见的排序算法的 Cheat Sheet.

O(n²) 复杂度的排序

对于排序的理解来说，我们需要能同时用直观的语言以及代码来进行描述。

排序问题可以总结为：

Input：N 个无序的元素（在 < 上有全序）。
Output：N 个有序的元素，按照从小到大。

我们先从 O(n²) 的排序开始。

选择排序 Selection Sort

用语言描述就是：

第 0 次，找出索引 [0, n-1] 中最小的，然后与 0 号位置的数交换。
第 1 次，找出索引 [1, n-1] 中最小的，然后与 1 号位置的数交换。
...
第 n -1 次，找出索引为 n-1 的最小值（此时只剩一个，因此不用交换）。

一共进行了 n 次交换，每次交换需要进行至多 n 次数组的整体查看。因此复杂度为 O(n²）。

用伪代码来描述：

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²)。

冒泡排序 Bubble Sort

用语言描述就是：

从第 0 位开始，比较相邻的两个数字。
- 如果前面的比后面的大，就交换它们的位置。
- 如果前面的小，就保持原样。
一次完整的比较后，最大的数字会到最后一位，就像泡泡从水中冒出来升到水面上方一样。
接着重复这个过程，但每次比较的范围缩小一位（因为最后的数字已经排序好了）。
直到没有需要交换的数字为止，排序完成。

用伪代码来描述：

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²）。

插入排序 Insertion Sort

用语言描述就是：

保证 [0,0] 上有序（已经完成）。
保证 [0,1] 上有序。
保证 [0,2] 上有序。
……
保证 [0, n-1] 上有序。

跟抓牌一样。

用伪代码来描述：

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²)，最好 O(n)

O(nlogn) 复杂度的排序

归并排序 Merge Sort

归并排序是一种递归式的排序。用语言描述就是：

先让左侧排序（递归步骤）
再让右侧排序（递归步骤）
然后整合整个数组（归并）

用代码描述的话是：

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 其实才是最重要也最容易犯错的部分。

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

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

简而言之，快速排序每次选择一个基准值，然后把比基准值小的扔到基准值的左边，比它大的扔到基准值的右边，然后对左右两边再 recursively 进行一次快速排序。

平均情况：O(n log n)

最好情况：O(n log n)

最坏情况：O(n²) - 当数组已经是排序状态，或者所有元素相等

交换操作

在这里特别介绍一下基于异或操作（^）的交换。我们可以通过下面的代码来进行数据的交换。

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

异或操作是一种位运算。它的性质是如果两位相等则异或结果为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

Algorithms #1 Sort

O(n²) 复杂度的排序

选择排序 Selection Sort

冒泡排序 Bubble Sort

插入排序 Insertion Sort

O(nlogn) 复杂度的排序

归并排序 Merge Sort

快速排序 Quick Sort

交换操作

最新文章

Comments

Lingheng Tony Tao