(Java)算法学习(二): 插入排序-排序过程拆解与算法优化

夕阳UPdz

1351人浏览 · 2025-08-01 22:28:50

夕阳UPdz · 2025-08-01 22:28:50 发布

始.插入排序的简单介绍

1.插入排序简介

插入排序是一种简单直观的排序算法，适用于小规模数据或部分有序的数据集。其核心思想是将未排序的元素逐个插入到已排序部分的适当位置

2.时间复杂度与空间复杂度

最优情况（已排序数组）：O(n)
平均和最坏情况（逆序数组）：O(n²)
插入排序是原地排序算法，空间复杂度为O(1)。

3.特点

稳定排序算法（相等元素相对位置不变）
适合小规模数据排序
实现简单，代码量少
在数据基本有序时效率较高

一.文字描述流程

变量定义与初始状态

定义变量 i 和 j，初始值均为 1。i 用于划分已排序区域（左侧）和未排序区域（右侧），j 用于在未排序区域中定位待排序数据。

示例数组

初始乱序数组：[5, 3, 8, 4, 2]

排序过程

第一轮外层循环（i = 1）

已排序区域：[5]
未排序区域：[3, 8, 4, 2]
待排序数据：arr[i] = 3
内层循环（j = i = 1）：
- 比较 arr[j-1] = 5 和 arr[j] = 3
- 若 arr[j-1] > arr[j]，交换两者，数组变为 [3, 5, 8, 4, 2]
- 检查 j 是否为 1（终止条件），结束内层循环
更新 i = 2

第二轮外层循环（i = 2）

已排序区域：[3, 5]
未排序区域：[8, 4, 2]
待排序数据：arr[i] = 8
内层循环（j = 2）：
- 比较 arr[j-1] = 5 和 arr[j] = 8
- 无需交换，直接终止内层循环
更新 i = 3

第三轮外层循环（i = 3）

已排序区域：[3, 5, 8]
未排序区域：[4, 2]
待排序数据：arr[i] = 4
内层循环（j = 3）：
- 比较 arr[j-1] = 8 和 arr[j] = 4，交换后数组为 [3, 5, 4, 8, 2]
- j 减 1 变为 2，继续比较 arr[j-1] = 5 和 arr[j] = 4，交换后数组为 [3, 4, 5, 8, 2]
- j 减 1 变为 1，终止内层循环
更新 i = 4

第四轮外层循环（i = 4）

已排序区域：[3, 4, 5, 8]
未排序区域：[2]
待排序数据：arr[i] = 2
内层循环（j = 4）：
- 依次比较并交换，最终数组变为 [2, 3, 4, 5, 8]
更新 i = 5，终止外层循环

最终结果

排序完成后的数组：[2, 3, 4, 5, 8]

可以发现,i是同时负责决定待排序元素和负责已排序区和未排序区的划分的，在i的左侧即已排序区域，而在y的右侧即为未排序区域，核心的排序逻辑是，i划分好区域和决定好待排序的元素，再由j带着待排序元素与已排序区逐个比较，并根据比较结果交换待排序元素并继续比较，直到j-1走到未排序区的末尾，j循环结束，i重新选择待排序元素............依次循环

二.代码实现

以下为插入排序的代码实现:

通过双层for循环嵌套，每次i决定好待排序元素和已排序区域后，就由j循环将待排序元素在已排序区域排好，然后i再次决定元素，直到i遍历完数组末尾。

public static void insert_sort(int[] arr) {
        //遍历数组-从头到尾
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >= 1; j--) {
                if (arr[j] < arr[j - 1]) {
                    /*如果当前数小于于前一个数->交换*/
                    MyMath.swap(arr, j, j - 1);
                }
            }
        }
    }

    /*交换值*/
    public static void swap(int[]arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

三.代码优化

代码问题：

上述的普通插入排序在排序过程中，每次j在前移之前，都会判断一下 j 是否大于 1 ，并且，即使我们当前的值是一个比待排序区里最大的值都要大的值，依旧会从当前位置向前继续排序进行判断，那么，有没有一种办法来优化掉这些无用判断，让插入排序变得更快的呢？

无监督的插入排序：

如果我们在整个排序过程中，先将一个最小值 minValue 移动到待排序数组的最前方的话，后续我们持续循环的条件就可以变更为 arr[j] < arr[j - 1] ，这样的插入排序，我们称之为“无监督的插入排序”。

优化后的代码实现：

    public static void unguarded_insert_sort(int[] arr) {
        //区别是:先将最小值找到并放在第一位,之后便不需要判断 j > 1
        int minIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[minIndex] > arr[i]) {
                minIndex = i;
            }
        }
        while (minIndex > 0) {
            MyMath.swap(arr, minIndex, minIndex - 1);
            minIndex -= 1;
        }
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (arr[j] < arr[j - 1]) {
                MyMath.swap(arr, j, j - 1);
                j--;
            }
        }
    }

为什么将最小值前置这一步步选择直接交换二者位置，而是一点点把最小值交换到第一位呢？

1.保持排序稳定性

逐步交换能维持排序算法的稳定性。直接交换可能破坏其他元素的相对顺序，而逐步交换确保每次只移动一个位置，避免大规模元素位移导致的稳定性问题。

2.减少复杂度突变

直接交换需要处理可能的大范围元素移动，增加时间复杂度。逐步交换每次只处理相邻元素，时间复杂度稳定在O(1)每次操作，整体仍为O(n^2)。

3.代码统一性

后续插入排序部分同样采用逐步交换策略。前置步骤与主体逻辑保持一致，减少代码分支和特殊处理，提高可读性和可维护性。

4.避免边界问题

逐步交换能自然处理数组边界条件。直接交换可能引发索引越界或未定义行为，尤其在最小值已位于首位时。

四.性能测试

1.性能对比

接下来,我会分别使用：100个元素的乱序数组，1000个元素的乱序数组，10000个元素的乱序数组以及100000个元素的乱序数组分别对普通插入排序和无监督插入排序进行性能测试。

测试结果如下：

插入排序:100个元素,排序成功! 
运行时间:1.0ms

无监督插入排序:100个元素,排序成功! 
运行时间:1.0ms

===============================

插入排序:1000个元素,排序成功! 
运行时间:7.0ms

无监督插入排序:1000个元素,排序成功! 
运行时间:6.0ms

===============================

插入排序:10000个元素,排序成功! 
运行时间:87.0ms

无监督插入排序:10000个元素,排序成功! 
运行时间:15.0ms

===============================

插入排序:100000个元素,排序成功! 
运行时间:5265.0ms

无监督插入排序:100000个元素,排序成功! 
运行时间:1204.0ms

===============================

2.原因分析

可以看到在面对(100-1k)的数据规模时，差距并不明显，但在从(10k-100k及以上)的数据规模下，二者开始出现了极大的差距，在面对十万个数据的排序时，时间居然差距在4倍以上,原因在于无监督的插入排序将判断条件从原来的每移动一次元素，变更为了每交换一次元素，大幅降低了它的时间复杂度，使得它在面对越大规模的数据，与普通插入排序的差距体现就越明显。