C++插入排序算法实例详解

什么是插入排序算法？

插入排序算法是一种简单直观的排序算法，其基本思想是将待排序的数据插入已排序序列的合适位置，以达到排序的目的。该算法的时间复杂度为 O(N^2)，适用于数据量较小的排序场景。

插入排序算法的基本步骤

插入排序算法的基本步骤可以归纳为以下三个：

1. 将待排序序列的第一个元素视作已排序序列，将后面的元素逐个与已排序序列中的元素比较，并将其插入合适的位置。

2. 依次将待排序序列中的其他元素插入已排序序列的恰当位置，直到待排序元素全部插入完成。

3. 完成排序，输出排好序的结果。

C++插入排序算法实例

下面是一段使用 C++ 语言实现插入排序算法的代码：

#include<iostream>
using namespace std;

void insertionSort(int arr[], int n)
{
    int i, j, key;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main()
{
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);

    cout << "排序后的数组：" << endl;
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

该程序中，insertionSort() 函数是实现插入排序的核心代码，程序首先定义了一个待排序的数组 arr，接着调用 insertionSort() 函数进行排序。排序结束后，程序输出排序后的数组。

示例说明

示例一

假设有一个待排序序列 arr[]={5,8,2,7,1,3,6,4}，使用插入排序算法后，得到的排序序列为 1,2,3,4,5,6,7,8。

详细过程：

1. 第一次排序后得到 arr[]={5,8,2,7,1,3,6,4}，此时已排序部分只包含一个元素 5。

2. 将待排序部分的下一个元素 8 与已排序部分的唯一元素 5 进行比较，发现 8 大于 5，故将 8 插入已排序部分的最后面，此时已排序部分变为 5,8。

3. 将待排序部分的下一个元素 2 与已排序部分中的元素进行比较，先将 8 向后移一位，再将 5 向后移一位，将 2 插入到已排序序列的第一位，此时已排序部分变为 2,5,8。

4. 依次对剩余元素进行插入排序，最终得到排序序列为 1,2,3,4,5,6,7,8。

示例二

假设有一个待排序序列 arr[]={1,2,3,4,5}，使用插入排序算法后，得到的排序序列与原序列相同，为 1,2,3,4,5。

详细过程：

1. 第一次排序后得到 arr[]={1,2,3,4,5}，此时已排序部分包含整个待排序序列。

2. 算法直接结束，输出原序列即可。

总结

插入排序算法是一种简单高效的排序算法，虽然其时间复杂度较高，但在数据规模较小的情况下表现较好。在实际开发中，需要根据不同的场景选择不同的排序算法，合理选取排序算法可以极大地提高程序的运行效率。