插入排序
1. 排序简介
排序是计算机科学中最基本的内容之一。想象一下，你有一堆考试卷子，需要按学生姓名的字母顺序排列，这就是排序！排序的核心是将一组数据（如数字或名字）按照特定顺序（通常是升序或降序）排列。为什么要排序？因为有序数据可以加速搜索（比如二分查找），还能让信息组织得更清晰。
我们聚焦于基于比较的排序，即仅使用比较运算符（如>和<）来决定元素的顺序。没有像哈希啥的高级技巧，只有纯粹的比较操作。我们还关注内部排序，意味着所有数据都在主内存（RAM）中处理，暂时不用考虑外部存储（如硬盘）。
以下是一个排序算法的基本函数签名（为简单起见，假设输入是整数数组）：
2. 插入排序
2.1 什么是插入排序？
插入排序非常直观，就像整理一手扑克牌。你从一张牌开始（已经“有序”），然后拿起下一张牌，插入到已排序的牌中正确的位置，重复这个过程直到所有牌都排好序。简单吧？
以下是插入排序代码：
void InsertionSort(ElementType A[], int N)
{
int j, P;
ElementType Tmp;
for (P = 1; P < N; P++) {
Tmp = A[P]; /* 下一张待插入的牌 */
for (j = P; j > 0 && A[j - 1] > Tmp; j--)
A[j] = A[j - 1]; /* 将已排序的牌向右移动，腾出位置 */
A[j] = Tmp; /* 将新牌插入到正确位置 */
} /* P循环结束 */
}
2.2 它是如何工作的？
我们一步步拆解：
- 从小处着手：第一个元素（
A[0]）被认为已排序。 - 挑选并插入：从
A[1]到A[N-1]的每个元素：- 将当前元素存入
Tmp（就像拿起一张牌）。 - 将已排序部分（从0到P-1）中比
Tmp大的元素向右移一位。 - 将
Tmp插入到合适的位置（左边都比它小，右边都比它大）。
- 将当前元素存入
- 重复：持续进行直到整个数组有序。
示例：排序 [5, 2, 4, 6, 1, 3]
- 第1轮：[5, 2, 4, 6, 1, 3] → [2, 5, 4, 6, 1, 3]（插入2）
- 第2轮：[2, 5, 4, 6, 1, 3] → [2, 4, 5, 6, 1, 3]（插入4）
- 第3轮：[2, 4, 5, 6, 1, 3] → [2, 4, 5, 6, 1, 3]（插入6）
- 第4轮：[2, 4, 5, 6, 1, 3] → [1, 2, 4, 5, 6, 3]（插入1）
- 第5轮：[1, 2, 4, 5, 6, 3] → [1, 2, 3, 4, 5, 6]（插入3）
2.3 时间复杂度
- 最坏情况：如果数组是逆序的（例如
[6, 5, 4, 3, 2, 1]），每次插入都需要移动几乎整个已排序部分。平均每次移动约N/2个元素，循环N次，总时间为O(N²)。 - 最佳情况：如果数组已经有序（例如
[1, 2, 3, 4, 5, 6]），每次插入只需比较一次，不需移动元素，仅需N次比较，因此时间为O(N)。
所以，插入排序在小型或接近有序的列表上表现很好，但在大型、混乱的列表上就慢得让人抓狂。
3. 逆序对：深入理解
3.1 什么是逆序对？
逆序对（inversion）是指数组中两个元素顺序错误的配对。形式上，对于索引i和j，如果i < j但A[i] > A[j]，这就是一个逆序对。可以把它看成排序需要修复的“错误”。
示例：数组[34, 8, 64, 51, 32, 21]
列出所有逆序对：
- (34, 8)、(34, 32)、(34, 21)
- (64, 51)、(64, 32)、(64, 21)
- (51, 32)、(51, 21)
- (32, 21)
共9个逆序对。
3.2 逆序对与插入排序
有趣的是，插入排序每次交换两个相邻的逆序元素时，恰好修复一个逆序对。所以，逆序对的数量直接决定了插入排序的工作量。
- 逆序对与时间复杂度：如果数组有
I个逆序对，插入排序的时间复杂度为O(I + N)。这里的N来自外层循环（检查每个元素），I是总的移动次数（每个逆序对对应一次移动）。 - 为什么接近有序时更快：如果列表几乎有序，
I很小，时间接近O(N)。但如果是逆序排列，I最大可达N(N-1)/2，时间回到O(N²)。
4. 简单排序算法的下界
4.1 逆序对的平均数量
定理：对于N个不同数字的数组，平均逆序对数量为N(N-1)/4。
- 为什么？在随机排列中，任意一对元素有50%的概率是逆序的。总共有N(N-1)/2个可能的配对，所以平均逆序对数是(1/2) * N(N-1)/2 = N(N-1)/4。
- 示例：当N = 4，平均逆序对数 = 4*3/4 = 3。
4.2 下界定理
定理：任何仅通过交换相邻元素的排序算法，平均时间复杂度为Ω(N²)。
- 证明概要：由于每次交换只修复一个逆序对，而平均有N(N-1)/4 ≈ N²/4个逆序对，至少需要这么多交换。因此，时间复杂度是二次方的。
4.3 这意味着什么？
对于像插入排序或冒泡排序这样仅交换相邻元素的“简单”算法，平均时间复杂度注定是O(N²)。无论我们多聪明，只要局限于相邻交换，就逃不出这个下界。
5. 突破限制：加速排序
那么，如何让排序比O(N²)更快？提示是：交换相距较远的元素。如果我们能通过一次交换修复多个逆序对，就能打破N²的限制。这引出了更高级的算法：
- 归并排序：将数组分割，分别排序，然后合并，时间复杂度为O(N log N)。
- 快速排序：选择一个枢纽，分区数组，然后递归处理，平均时间为O(N log N)。
这些算法不再只调整相邻元素，而是通过大规模重组来一次性修复大量逆序对。