本文共 1163 字，大约阅读时间需要 3 分钟。

插入排序是一种经典的排序算法，以其简单易懂的思想和稳定性著称。尽管实现起来相对较为复杂，但它在某些场景下仍然被广泛使用。

插入排序的基本思想是通过将元素插入到有序序列中的适当位置来实现排序。具体而言，我们将数组分为三个部分：待插入序列、待插元素和剩余元素组。通过逐步将待插元素插入到正确位置，我们可以逐步完成排序。

让我们以一个简单的例子来理解这个过程。假设我们有一个数组[4, 3, 2, 1]，我们可以将其分为三组：

• 待插入序列：4, *3（*3表示一个占位符，用于表示即将插入的位置）
• 待插元素：3
• 剩余元素组：2, 1

通过逐步插入，我们可以看到插入排序的过程。首先，从第二个元素开始，我们进入第一趟插入排序的循环。对于每个元素，我们都会检查它与当前已排序部分的元素关系，并将其插入到正确的位置。

在代码实现中，我们可以使用一个外层循环控制插入的次数（总共需要进行n-1次插入）。内层循环则负责将当前元素插入正确位置。具体来说，我们从数组的第二个元素开始，逐步将元素向前移动，直到找到合适的位置。

插入的关键点在于，如果当前元素比前一个元素小，我们就将前一个元素向后移动一个位置，并继续比较；否则，我们结束当前插入循环，并将元素插入到当前位置。

通过这种方式，我们可以逐步完成数组的排序。插入排序的时间复杂度为O(n²)，稳定性也较高，因为每次插入都不会破坏前面的元素顺序。

以下是实现代码：

template
   
    void myInsertSort(T array[], int len) {    for (int i = 1; i < len; ++i) {        int j = i;        T temp = array[i];        while (j > 0) {            if (temp < array[j-1]) {                array[j] = array[j-1];                j--;            } else {                break;            }        }        array[j] = temp;    }}
   

测试代码如下：

int a[] = {2, 6, 8, 4, 7, 10, 1};int len = sizeof(a) / sizeof(a[0]);myInsertSort(a, len);for (int i = 0; i < len; ++i) {    cout << a[i] << endl;}

通过上述代码，我们可以看到插入排序的实际运行效果。每一次循环都会将一个元素插入到正确的位置，最终完成整个数组的排序。

转载地址：http://klzz.baihongyu.com/