c++插入排序

#include <iostream>
#include <vector>

using namespace std;

// 插入排序算法的实现
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        // 将当前元素插入到已排序部分的正确位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6};
    cout << "排序前: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    insertionSort(arr);

    cout << "排序后: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

解释说明

1. 插入排序的基本思想:

   • 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

2. 代码解释:

   • insertionSort 函数实现了插入排序算法。它遍历数组中的每个元素，并将其插入到前面已经排序好的子数组中。
   • main 函数用于测试插入排序算法。首先定义一个待排序的数组，然后调用 insertionSort 函数进行排序，最后输出排序前后的数组。

3. 关键步骤:

   • 外层循环 for (int i = 1; i < n; ++i) 从第二个元素开始遍历数组。
   • 内层循环 while (j >= 0 && arr[j] > key) 将当前元素 key 插入到已排序部分的正确位置。
   • 最终将 key 插入到合适的位置，完成一次插入操作。

希望这段代码和解释对你理解插入排序有所帮助！