【一周一算法】第二周：选择排序与插入排序

🧮 一周一个算法 · 第 2 周

选择排序与插入排序 —— 从“挑选”与“插入”看排序的两种哲学

“冒泡排序靠交换相邻元素逐步推进，
选择排序靠挑选最值一步到位，
插入排序靠不断调整插入位置，
—— 三者合称：排序算法的三剑客。”

---

🧭 一、引言：为什么还要研究 $O(n^2)$ 算法？

很多人觉得这些算法“太简单”或“太慢”，但实际上——
它们是后续所有排序算法的核心雏形：

算法	启发思想	后继算法
冒泡排序	相邻交换	快速排序（基于交换）
选择排序	找最小元素	堆排序（基于选择）
插入排序	有序插入	希尔排序 / 二分插入排序

学习这三种算法 = 搞懂所有复杂排序的“原型逻辑”。

---

🧩 二、选择排序（Selection Sort）

🧠 核心思想

每一趟从未排序部分中“选出最小值”，放到前面。

形象类比：
像每次在乱序的卡片中挑出最小的一张，放到有序区末尾。

示例：

初始: [29, 10, 14, 37, 13]
第1轮: 选出10 -> [10, 29, 14, 37, 13]
第2轮: 选出13 -> [10, 13, 14, 37, 29]
第3轮: 选出14 -> [10, 13, 14, 37, 29]
第4轮: 选出29 -> [10, 13, 14, 29, 37]

---

⚙️ 伪代码

procedure SelectionSort(A[0..n-1]):
    for i from 0 to n-2:
        minIndex ← i
        for j from i+1 to n-1:
            if A[j] < A[minIndex]:
                minIndex ← j
        swap(A[i], A[minIndex])

---

💻 C++ 实现

#include <iostream>
#include <vector>
#include <utility>

void selectionSort(std::vector<int>& arr) {
    size_t n = arr.size();
    for (size_t i = 0; i < n - 1; ++i) {
        size_t minIndex = i;
        for (size_t j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        if (minIndex != i)
            std::swap(arr[i], arr[minIndex]);
    }
}

int main() {
    std::vector<int> arr = {29, 10, 14, 37, 13};
    selectionSort(arr);

    std::cout << "排序结果：";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
}

输出：

排序结果：10 13 14 29 37

---

📈 时间复杂度分析

• 比较次数：固定 $((n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2})$
• 交换次数：最多 $n-1$ 次
• 时间复杂度：

  $$T(n) = O(n^2)$$

• 空间复杂度：

  $$S(n) = O(1)$$

• 稳定性：❌ 不稳定（同值元素可能被交换顺序打乱）

---

✳️ 数学视角：交换次数之少

选择排序交换次数最少：

• 每次只在确定位置后交换 1 次；
• 总交换次数 $\leq n-1$；

相比冒泡排序可能交换上千次，选择排序“节省了手臂动作”😄。

---

🔸 三、插入排序（Insertion Sort）

🧠 核心思想

构建一个“有序区”，每次把新的元素插入到合适位置。

示例：

初始: [5, 2, 4, 6, 1, 3]
第1轮: [2, 5, 4, 6, 1, 3]
第2轮: [2, 4, 5, 6, 1, 3]
第3轮: [2, 4, 5, 6, 1, 3]
第4轮: [1, 2, 4, 5, 6, 3]
第5轮: [1, 2, 3, 4, 5, 6]

就像你打扑克牌时，拿到新牌后插到正确的位置。

---

⚙️ 伪代码

procedure InsertionSort(A[0..n-1]):
    for i from 1 to n-1:
        key ← A[i]
        j ← i - 1
        while j ≥ 0 and A[j] > key:
            A[j + 1] ← A[j]
            j ← j - 1
        A[j + 1] ← key

---

💻 C++ 实现

#include <iostream>
#include <vector>

void insertionSort(std::vector<int>& arr) {
    size_t n = arr.size();
    for (size_t i = 1; i < n; ++i) {
        int key = arr[i];
        int j = static_cast<int>(i) - 1;

        // 向右移动比 key 大的元素
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

int main() {
    std::vector<int> arr = {5, 2, 4, 6, 1, 3};
    insertionSort(arr);

    std::cout << "排序结果：";
    for (int num : arr) std::cout << num << " ";
    std::cout << std::endl;
}

输出：

排序结果：1 2 3 4 5 6

---

📈 时间复杂度分析

情况	比较次数	时间复杂度
最好（已排序）	$n-1$	$O(n)$
平均	$n^2/4$	$O(n^2)$
最坏（逆序）	$n^2/2$	$O(n^2)$

空间复杂度：

$$S(n) = O(1)$$

稳定性：
✅ 稳定（相等元素不会被交换顺序）

---

🔢 数学推导：平均复杂度为何是 $O(n^2/4)$？

平均情况下，插入时一半的元素需要移动：

$$\frac{1}{n} \sum_{i=1}^{n} \frac{i}{2} = \frac{n^2}{4}$$

所以：

$$T(n) \approx \frac{1}{4} n^2 \Rightarrow O(n^2)$$

这说明插入排序在部分有序的数组中效率非常高。

---

🔍 四、两者对比总结

特性	选择排序	插入排序
思想	每次挑最小	每次插入新元素
比较次数	固定 $O(n^2)$	平均 $O(n^2/4)$
交换次数	$\leq n-1$	最坏 $O(n^2)$ 移动
稳定性	❌ 不稳定	✅ 稳定
最好情况	$O(n^2)$	$O(n)$
适用场景	小数组，无序度高	部分有序、小规模
工程意义	启发堆排序	启发希尔排序

---

🧠 五、思考题与练习

1. 为什么选择排序即使数组已排序也不会提前终止？
2. 如果我们使用二分查找寻找插入位置，插入排序的复杂度能否变成 $O(n \log n)$？（提示：移动操作仍然需要 $O(n)$）
3. 请实现一个泛型模板版的 insertionSort<T>，支持自定义比较函数。

---

🌱 六、延伸阅读

• 《算法导论》第 2 章：插入排序分析
• 《Data Structures and Algorithms in C++》：排序策略比较
• LeetCode 推荐：
  • #147. Insertion Sort List
  • #912. Sort an Array

---

✨ 七、总结

指标	选择排序	插入排序
时间复杂度	$O(n^2)$	$O(n^2)$，最好 $O(n)$
空间复杂度	$O(1)$	$O(1)$
稳定性	否	是
适用性	简单、对交换代价敏感	部分有序、小规模场景

🧩 “选择排序注重决策，插入排序注重适应。
在算法的世界里，这两种思维是最早的智慧火花。”

---

🔜 下周预告

第 3 周：归并排序（Merge Sort）——分治思想的第一次登场
我们将深入剖析递归与分治策略，用数学方式理解为什么“分而治之”如此强大。