插入排序，如一位细心的整理者，
她从序列的左端开始，
挨个将元素归位。

每当她遇到一个无序的元素，
便将它插入已经有序的部分，
直至所有元素有序排列。

她不张扬，却有效率，
用自己的方式，
为序列找到了平衡与秩序。

文章目录

• 一、插入排序
• 二、发展历史
• 三、处理流程
• 四、算法实现
• 五、插入排序的特性
• 推荐阅读

一、插入排序

插入排序是一种简单直观的排序算法。插入排序的思想类似于我们打扑克牌时的排序过程：每次从未排序的牌堆中取出一张牌，并插入到已排序的牌堆中的正确位置。

具体来说，插入排序的过程如下：

1. 将数组分成已排序区间和未排序区间，初始时已排序区间只包含第一个元素。
2. 从未排序区间取出一个元素，依次与已排序区间的元素比较，找到合适的位置插入。
3. 将该元素插入到已排序区间的正确位置。
4. 重复步骤 $2$

二、发展历史

插入排序作为最简单直观的排序算法之一，其历史可以追溯到古代。然而，现代计算机科学中对插入排序的形式化描述和分析是在

20

20

20 世纪中叶开始的。

1. 古代： 插入排序的概念可能可以追溯到古代，人们在整理和排序物品时可能会采用类似的方法。例如，根据字母顺序整理书籍或文件。
2. $1950$
3. $1960$
4. $1970$

三、处理流程

场景假设：我们需要将下面的无序序列使用插入排序按从小到大进行排序。

1. 第

   1

   1

   1 轮插入：默认第

   1

   1

   1 个元素处于已排序区间，取未排序区间中第

   1

   1

   1 个元素（即：

   2

   2

   2）为基准，将元素

   2

   2

   2 插入到已排序区间正确位置

2. 第

   2

   2

   2 轮插入：取未排序区间中第

   1

   1

   1 个元素（即：

   1

   1

   1）为基准，将元素

   1

   1

   1 插入到已排序区间正确位置

3. 第

   3

   3

   3 轮插入：取未排序区间中第

   1

   1

   1 个元素（即：

   5

   5

   5）为基准，将元素

   5

   5

   5 插入到已排序区间正确位置

4. 第

   4

   4

   4 轮插入：取未排序区间中第

   1

   1

   1 个元素（即：

   3

   3

   3）为基准，将元素

   3

   3

   3 插入到已排序区间正确位置

四、算法实现

void insertionSort(int[] arr) {
    int n = arr.length; // 获取数组长度
    
    // 从第二个元素开始，依次将元素插入到已排序序列中
    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]; // 将 arr[j] 向右移动一位
            j--; // 继续向前遍历
        }
        arr[j + 1] = key; // 将当前待插入的元素插入到合适的位置
    }
}

算法时间复杂度分析：

五、插入排序的特性

插入排序具有以下特性：

1. 稳定性： 插入排序是一种稳定的排序算法，即相等元素的相对位置在排序前后保持不变。
2. 原地性： 插入排序是一种原地排序算法，它只需要常数级别的额外空间来存储少量的辅助变量，而不需要额外的数组空间。
3. 适用性： 对于小规模数组或部分有序的数组，插入排序是一个简单且高效的排序算法。但在处理大规模数据集时，插入排序的性能通常不如快速排序、归并排序等高级排序算法。

推荐阅读

1. Spring 三级缓存
2. 深入了解 MyBatis 插件：定制化你的持久层框架
3. Zookeeper 注册中心：单机部署
4. 【JavaScript】探索 JavaScript 中的解构赋值
5. 深入理解 JavaScript 中的 Promise、async 和 await