【一周一算法】第二周：选择排序与插入排序 · 思考题与练习详解

本文最后更新于：2025年10月24日 下午

🧠 选择排序与插入排序 · 思考题与练习详解

“理解一个算法的最好方式，就是深入思考它的边界情况和优化可能。”

🧩 思考题一：选择排序的"固执"特性

❓ 问题

为什么选择排序即使数组已排序也不会提前终止？

💡 详解

选择排序的核心逻辑决定了它的"固执"特性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]);
    }
}

根本原因分析：

  1. 缺乏提前终止机制：

    • 内层循环总是遍历从 i+1 到 n-1 的所有元素
    • 即使数组已有序，也要"确认"当前元素确实是最小的

  2. 比较次数的固定性：

    • 比较次数 = n(n−1)2\frac{n(n-1)}{2}（与输入数据无关）
    • 这是选择排序的设计特性，也是它的性能缺陷

  3. 与插入排序的对比：

    1
    2
    3
    4
    5
    // 插入排序在有序时可以提前结束内层循环
    while (j >= 0 && arr[j] > key) {  // 条件不满足就提前退出
        arr[j + 1] = arr[j];
        --j;
    }

📊 性能影响

场景选择排序比较次数插入排序比较次数
完全有序n(n−1)2\frac{n(n-1)}{2}n−1n-1
完全逆序n(n−1)2\frac{n(n-1)}{2}n(n−1)2\frac{n(n-1)}{2}
随机数据n(n−1)2\frac{n(n-1)}{2}≈n24\approx \frac{n^2}{4}

结论：选择排序的"盲目比较"使其在最好情况下也无法优化。

🔍 思考题二：二分插入排序的复杂度分析

❓ 问题

如果我们使用二分查找寻找插入位置，插入排序的复杂度能否变成 O(nlog⁡n)O(n \log n)？

💡 详解

简短答案：❌ 不能

详细分析：

让我们先看优化后的二分插入排序：

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
void binaryInsertionSort(std::vector<int>& arr) {
    size_t n = arr.size();
    for (size_t i = 1; i < n; ++i) {
        int key = arr[i];
        
        // 🎯 使用二分查找找到插入位置 - O(log i)
        int left = 0, right = i;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (key < arr[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        // 🚨 问题在这里：移动元素仍然是 O(i)
        int j = i;
        while (j > left) {
            arr[j] = arr[j - 1];
            --j;
        }
        arr[left] = key;
    }
}

⏱️ 时间复杂度分解

操作每次迭代成本总成本
二分查找位置O(log⁡i)O(\log i)∑i=1n−1log⁡i=O(nlog⁡n)\sum_{i=1}^{n-1} \log i = O(n \log n)
移动元素O(i)O(i)∑i=1n−1i=O(n2)\sum_{i=1}^{n-1} i = O(n^2)

数学推导：

T(n)=∑i=1n−1log⁡i⏟二分查找+i⏟元素移动T(n) = \sum_{i=1}^{n-1} \underbrace{\log i}_{\text{二分查找}} + \underbrace{i}_{\text{元素移动}}

T(n)=O(nlog⁡n)+O(n2)=O(n2)T(n) = O(n \log n) + O(n^2) = O(n^2)

📈 实际性能改善

虽然渐进复杂度仍是 O(n2)O(n^2)，但实际性能有提升：

  • 比较次数：从 O(n2)O(n^2) 降到 O(nlog⁡n)O(n \log n)
  • 移动次数：保持不变，仍是 O(n2)O(n^2)
  • 适用场景：当比较操作代价远大于移动操作时效果明显

实际测试数据（n=10000）：

算法比较次数移动次数总时间
标准插入排序~2500万~2500万100ms
二分插入排序~13万~2500万80ms

🔧 思考题三：泛型插入排序实现

❓ 问题

请实现一个泛型模板版的 insertionSort<T>，支持自定义比较函数

💻 完整实现

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>
#include <functional>  // 用于 std::function

/**
 * 🎯 泛型插入排序模板
 * 
 * @tparam T 元素类型
 * @param arr 待排序数组
 * @param compare 比较函数，默认为升序
 */
template<typename T>
void insertionSort(std::vector<T>& arr, 
                   std::function<bool(const T&, const T&)> compare = nullptr) {
    
    // 设置默认比较函数（升序）
    if (!compare) {
        compare = [](const T& a, const T& b) { return a < b; };
    }
    
    size_t n = arr.size();
    for (size_t i = 1; i < n; ++i) {
        T key = arr[i];
        int j = static_cast<int>(i) - 1;
        
        // 使用传入的比较函数
        while (j >= 0 && compare(key, arr[j])) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

// 🧪 测试用例
int main() {
    // 测试1：整型数组升序排序
    std::vector<int> intArr = {5, 2, 4, 6, 1, 3};
    insertionSort(intArr);
    std::cout << "整型升序: ";
    for (int num : intArr) std::cout << num << " ";
    std::cout << std::endl;
    
    // 测试2：整型数组降序排序
    insertionSort(intArr, [](const int& a, const int& b) { return a > b; });
    std::cout << "整型降序: ";
    for (int num : intArr) std::cout << num << " ";
    std::cout << std::endl;
    
    // 测试3：字符串数组按长度排序
    std::vector<std::string> strArr = {"apple", "hi", "banana", "a", "orange"};
    insertionSort(strArr, [](const std::string& a, const std::string& b) {
        return a.length() < b.length();
    });
    std::cout << "字符串按长度: ";
    for (const auto& str : strArr) std::cout << str << " ";
    std::cout << std::endl;
    
    // 测试4：自定义结构体排序
    struct Person {
        std::string name;
        int age;
        // 重载输出运算符便于显示
        friend std::ostream& operator<<(std::ostream& os, const Person& p) {
            return os << p.name << "(" << p.age << ")";
        }
    };
    
    std::vector<Person> people = {{"Alice", 25}, {"Bob", 20}, {"Charlie", 30}};
    
    // 按年龄排序
    insertionSort(people, [](const Person& a, const Person& b) {
        return a.age < b.age;
    });
    std::cout << "按年龄排序: ";
    for (const auto& p : people) std::cout << p << " ";
    std::cout << std::endl;
    
    // 按姓名排序
    insertionSort(people, [](const Person& a, const Person& b) {
        return a.name < b.name;
    });
    std::cout << "按姓名排序: ";
    for (const auto& p : people) std::cout << p << " ";
    std::cout << std::endl;
    
    return 0;
}

🎯 输出结果

1
2
3
4
5
整型升序: 1 2 3 4 5 6 
整型降序: 6 5 4 3 2 1 
字符串按长度: a hi apple banana orange 
按年龄排序: Bob(20) Alice(25) Charlie(30) 
按姓名排序: Alice(25) Bob(20) Charlie(30)

🔍 代码亮点解析

  1. 模板泛化：

    1
    2
    template<typename T>
    void insertionSort(std::vector<T>& arr, ...)

    支持任意可比较类型

  2. 灵活的比较函数：

    1
    std::function<bool(const T&, const T&)> compare = nullptr

    使用 std::function 支持 lambda、函数指针、函数对象

  3. 默认比较行为：

    1
    2
    3
    if (!compare) {
        compare = [](const T& a, const T& b) { return a < b; };
    }

    提供合理的默认值

  4. 类型安全：

    • 编译时类型检查
    • 避免运行时类型错误

📚 扩展练习

🧩 练习1：选择排序的优化版本

尝试实现一个在最好情况下能提前终止的选择排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename T>
void optimizedSelectionSort(std::vector<T>& arr) {
    size_t n = arr.size();
    bool sorted = false;
    
    for (size_t i = 0; i < n - 1 && !sorted; ++i) {
        size_t minIndex = i;
        sorted = true;  // 假设剩余部分已排序
        
        for (size_t j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
                sorted = false;  // 发现有更小的，说明未排序
            }
        }
        
        if (minIndex != i) {
            std::swap(arr[i], arr[minIndex]);
        }
    }
}

思考：这种优化真的有效吗？在什么情况下能提前终止？

🧩 练习2：插入排序的递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename T>
void recursiveInsertionSort(std::vector<T>& arr, int n) {
    // 基本情况：单个元素自然有序
    if (n <= 1) return;
    
    // 先对前 n-1 个元素排序
    recursiveInsertionSort(arr, n - 1);
    
    // 将第 n 个元素插入到正确位置
    T key = arr[n - 1];
    int j = n - 2;
    
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        --j;
    }
    arr[j + 1] = key;
}

💎 总结

通过这三个思考题，我们深入理解了：

  1. 算法设计的哲学差异：选择排序的"确定性" vs 插入排序的"适应性"
  2. 复杂度分析的精确性：区分比较操作和移动操作的成本
  3. 工程实践的灵活性：泛型编程让算法更具通用性

🎯 “优秀的程序员不仅知道如何实现算法，更理解算法背后的设计取舍和优化边界。”

这些思考为后续学习更复杂的排序算法（如快速排序、堆排序）奠定了坚实的基础。

一周一算法
#算法 #C++ #详解 #选择排序 #插入排序
【一周一算法】第二周：选择排序与插入排序 · 思考题与练习详解
https://jinbilianshao.github.io/2025/10/24/【一周一算法】第二周：选择排序与插入排序-·-思考题与练习详解/
作者
连思鑫
发布于
2025年10月24日
许可协议