图解Java中插入排序算法的原理与实现

插入排序算法的原理与实现

一、插入排序算法的原理

插入排序是一种简单的排序算法，其基本思想是构建有序序列，对于未排序的数据，在已排序的序列中从后向前扫描，找到相应位置插入。插入排序和冒泡排序一样，也属于交换排序的一种。

插入排序的核心思想是将未排序的数据插入有序序列中的合适位置，具体分以下两个步骤：

1. 从第一个元素开始，默认这个元素是有序的序列，将下一个元素与有序序列进行比较，找到插入的位置，使得插入后依然保持有序序列；
2. 重复上述步骤，将未排序的元素插入到有序序列中。

思路比较简单，算法实现也比较直观。下面让我们来看看插入排序算法的具体实现过程。

二、插入排序算法的实现

以下是插入排序算法的标准实现过程，使用Java语言编写：

public static void insertSort(int[] arr) {
    int len = arr.length;
    for (int i = 1; i < len; i++) {
        int j = i;
        int temp = arr[i];
        while (j > 0 && arr[j-1] > temp) {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = temp;
    }
}

代码分析

该算法使用 for 循环遍历整个数组，起始点为第一个元素。从第二个元素开始遍历，将其插入到已经排好序的序列中。在内层循环中，将当前元素值（temp）与前一个元素值（arr[j-1]）进行比较。如果前一个元素值较大，则将其后移一位，直到比较的元素为第一个元素或者当前元素值（temp）比前一个元素值（arr[j-1]）大为止。最后插入当前元素至正确位置，进入下一次循环。

三、插入排序算法的示例说明

1. 示例一

假设我们要对数组 [4, 6, 1, 5, 3, 9, 8, 2, 7] 进行排序。按照插入排序算法进行排序的过程如下：

1. 开始排序，将第一个元素 4 视为已经排序的序列；
2. 拿到第二个元素 6，将其与已经排序的序列进行比较，发现 6 大于 4，则将其放到前面，序列变为 [4, 6]；
3. 拿到第三个元素 1，将其与已经排序的序列进行比较，发现 1 小于 6，则将 6 后移一位，再将 4 后移一位，最后将 1 放入合适位置，序列变为 [1, 4, 6]；
4. 依次类推，重复上述步骤，直到遍历到数组的最后一个元素，排序完成。

最终得到的有序数组为 [1, 2, 3, 4, 5, 6, 7, 8, 9]。

2. 示例二

假设我们要对数组 [5, 4, 3, 2, 1] 进行排序。按照插入排序算法进行排序的过程如下：

1. 开始排序，将第一个元素 5 视为已经排序的序列；
2. 拿到第二个元素 4，将其与已经排序的序列进行比较，发现 4 小于 5，则将其放到前面，序列变为 [4, 5]；
3. 拿到第三个元素 3，将其与已经排序的序列进行比较，发现 3 小于 5，则将 5 后移一位，再将 4 后移一位，最后将 3 放入合适位置，序列变为 [3, 4, 5]；
4. 依次类推，重复上述步骤，直到遍历到数组的最后一个元素，排序完成。

最终得到的有序数组为 [1, 2, 3, 4, 5]。

四、总结

插入排序算法是一种简单的排序算法，其时间复杂度为 O(n^2)，比其他排序算法效率要低。但是该算法仍然有其优点，比如空间复杂度低，小规模数据效率高等等。在实际应用中，可以针对不同的数据规模和数据类型选择不同的排序算法，以达到更好的排序效果。