C++插入排序详解（从零开始掌握经典排序算法）

具体来说，插入排序从数组的第二个元素开始，将其与前面已排序的部分逐个比较，找到合适的位置插入。重复这个过程，直到整个数组有序。

插入排序的步骤

1. 假设数组的第一个元素已经是“有序”的。
2. 从第二个元素开始，依次取出当前元素（称为“key”）。
3. 将 key 与前面已排序部分的元素从右向左比较。
4. 如果前面的元素大于 key，则将其向右移动一位。
5. 重复步骤4，直到找到小于或等于 key 的元素，将 key 插入其后。
6. 继续处理下一个元素，直到遍历完整个数组。

C++实现插入排序

下面是一个完整的C++排序教程代码示例，展示了如何用C++编写插入排序：

#include <iostream>#include <vector>void insertionSort(std::vector<int>& arr) {    int n = arr.size();    for (int i = 1; i < n; i++) {        int key = arr[i];        int j = i - 1;        // 将大于 key 的元素向右移动        while (j >= 0 && arr[j] > key) {            arr[j + 1] = arr[j];            j--;        }        arr[j + 1] = key; // 插入 key 到正确位置    }}// 打印数组void printArray(const std::vector<int>& arr) {    for (int num : arr) {        std::cout << num << " ";    }    std::cout << std::endl;}int main() {    std::vector<int> arr = {12, 11, 13, 5, 6};    std::cout << "排序前: ";    printArray(arr);    insertionSort(arr);    std::cout << "排序后: ";    printArray(arr);    return 0;}

代码解析

- insertionSort 函数接收一个整型 vector 引用。 - 外层循环从索引 1 开始（因为索引 0 被视为已排序）。 - 内层 while 循环负责将比 key 大的元素向右“腾出”位置。 - 最终将 key 插入到正确位置。

时间与空间复杂度

• 最好情况：数组已经有序，时间复杂度为 O(n)。
• 最坏情况：数组逆序，时间复杂度为 O(n²)。
• 平均情况：时间复杂度为 O(n²)。
• 空间复杂度：O(1)，属于原地排序算法。

适合初学者的排序算法

对于初学者C++排序学习者来说，插入排序是理解排序思想的绝佳起点。它稳定、直观，且在小规模数据或部分有序数据上表现良好。虽然在大数据集上效率不如快速排序或归并排序，但其简洁性使其成为教学和面试中的常客。

总结

通过本教程，你已经掌握了 C++ 插入排序的基本原理、实现方法和性能特点。建议你动手运行上面的代码，修改数组内容，观察排序过程，加深理解。掌握这一基础算法，将为你学习更复杂的C++插入排序变体和其他高级算法打下坚实基础！