【排序算法】之插入排序

一、算法介绍

插入排序是一种比较基础简单的算法，又叫直接插入排序法。其基本思想是将待排序的元素逐个插入到已排序的部分，最终得到一个有序序列。具体步骤如下：

假设数组的第一个元素已经是有序的。
从第二个元素开始，遍历整个数组。
对于每个未排序的元素，将其作为“关键值”（key）。
将关键值与已排序部分的元素从后向前逐个比较，找到第一个比关键值小的元素。
将所有比关键值大的元素向后移动一位，为关键值腾出位置。
将关键值插入到正确的位置。
重复步骤3-6，直到所有元素都插入到正确的位置。

插入排序的时间复杂度在最好的情况下（即输入数组已经有序）为O(n)，最坏的情况（即输入数组逆序）为O( n 2 n^{2} n2)，平均情况下的时间复杂度也是O( n 2 n^{2} n2)。虽然插入排序在大数据集上效率不如其他高级排序算法，但它对于小规模数据或者部分有序的数据有较好的性能，并且算法实现简单。

二、java代码示例

package com.datastructures;

import java.util.Arrays;

/**
 * 插入排序算法示例
 *
 * @author hulei
 * @date 2024/5/11 14:10
 */


public class InsertionSort {

    /**
     * 使用插入排序算法对一个可比较数组进行排序。
     * 该算法从数组的第二个元素开始，将其与之前的元素逐个比较并插入到正确的位置，直到整个数组排序完成。
     *
     * @param array 要排序的数组，数组元素必须实现Comparable接口，以便进行比较。
     * @param <E> 数组元素的类型，该类型需扩展Comparable接口，以支持元素之间的比较。
     */
    public static <E extends Comparable<? super E>> void insertionSortOne(E[] array) {
        // 遍历数组，从第二个元素开始进行排序
        for (int i = 1; i < array.length; i++) {
            E key = array[i]; // 当前需要排序的元素
            int j = i - 1; // 指向当前元素前一个位置的指针
            // 将大于key的元素依次后移，直到找到合适的位置插入key
            while (j >= 0 && key.compareTo(array[j]) < 0) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key; // 插入key到正确的位置
        }
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[]{20, 12, 27, 15, 18, 29, 11, 21, 34, 28, 23, 41, 39, 14, 6, 17};
        insertionSortTwo(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 使用插入排序算法对可比较元素数组进行排序。
     * 该算法会逐步将数组的每个元素插入到已排序序列的正确位置，从而逐步构建一个有序序列。
     *
     * @param array 要排序的元素数组，数组中的元素必须实现Comparable接口。
     */
    public static <E extends Comparable<? super E>> void insertionSortTwo(E[] array) {
        // 遍历数组，对每个元素执行插入排序
        for (int i = 0; i < array.length; i++) {
            // 将当前元素与已排序的元素逐个比较，找到正确的位置并插入
            for (int j = i; j > 0; j--) {
                // 如果当前元素小于前一个元素，则交换位置
                if (array[j].compareTo(array[j-1]) < 0) {
                    swap(array, j, j-1);
                } else {
                    // 如果当前元素不小于前一个元素，则停止比较
                    break;
                }
            }
        }
    }

    /**
     * 交换数组中两个元素的位置。
     *
     * @param array  要进行交换的数组。
     * @param index1 要交换的第一个元素的索引。
     * @param index2 要交换的第二个元素的索引。
     * @param <E>    数组元素的类型。
     */
    private static <E> void swap(E[] array, int index1, int index2) {
        // 临时变量用于存储第一个元素，以便后续交换
        E temp = array[index1];
        array[index1] = array[index2]; // 将第二个元素的值赋给第一个元素
        array[index2] = temp; // 将之前存储的第一个元素的值赋给第二个元素
    }

}

我采用了两种方法来实现排序，分别是insertionSortOne() 和insertionSortTwo()，这两个方法基本都实现了插入排序的算法特性，只是元素的处理方式不一样。我这里把核心代码详细解释下：

insertionSortOne

按照从小到大的顺序排序
本方法使用了替换元素值的方式。外层for循环主要是循环所有需要插入排序的位置，第一个元素默认已排序。外层for循环从第二个元素开始，内层的while循环则是从需要排序的元素开始，从后往前遍历，遇到之前的元素更大，就把当前位置的元素值替换成比它大的前一个元素。

假设现在要给数组 **[7，6，8，4，9]**排序，外层for循环i为1，即第二个元素6需要排序

 for (int i = 1; i < array.length; i++) {
            E key = array[i]; // 当前需要排序的元素
            int j = i - 1; // 指向当前元素前一个位置的指针
            // 将大于key的元素依次后移，直到找到合适的位置插入key
            while (j >= 0 && key.compareTo(array[j]) < 0) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key; // 插入key到正确的位置
        }

第一次for循环
此时i = 1， key = array[1] = 6，j = i-1 = 0，那么array[j] = array[0] = 7
while条件意思是 j必须大于等0，即最多只能和第一个索引位置元素比较才有意义。
比较得知array[j] >key，所以 key.compareTo(array[j]) < 0，进入while循环
array[j + 1] = array[j]，即把array[0+1] = array[1]位置的元素值替换为array[j] = array[0]位置的元素，
数组变为 [7，7，8，4，9]，array[0]仍然是7。
j 指针往前移动把 j 指针的前一个元素再与key比较，但j–变为-1了，-1索引是没有意义的，跳出while循环
array[j + 1] = key即把array[-1+1]= array[0]，位于第一个位置的值替换为key，把key插入到正确的位置了
数组变为 [6，7，8，4，9]

进入第二次for循环
此时 i = 2，key = array[2] = 8，j = i -1 =1，array[j] = array[1] = 7
显然key>array[j]，不进入while循环，array[j + 1] = key，即把array[1+1] = array[2] 位置和的元素替换为key的值，array[2]位置值本来就是key，所以此轮循环结束后
数组变为 [6，7，8，4，9]

第三次for循环
此时i = 3，key = array[3] = 4，j = i -1 =2，array[j] = array[2] = 8
key<array[j]，第一次进入while循环，array[j+1]位置值替换为array[j]的值8，数组为 [6，7，8，8，9]，j–变为1，
此时array[j] = array[1] = 7，key<7 ，再次进入while循环
array[j+1]的位置替换为array[j]，即array[2] = 7，数组变为***[6，7，7，8，9]，
j–变为0，并且key<array[0] = 6，第三次进入while循环，array[j+1]的位置替换为array[j]即array[1] = 6，数组为[6，6，7，8，9]***
j–变为-1，跳出while循环，然后把array[j+1] = array[0]位置的值替换为key
整个数组第三次for循环排序结束变为
[4，6，7，8，9]

第四次for循环
即对第五个也是最后一个元素进行排序，此时i =4 ，key = array[4] = 9，j = i -1 =3，array[j] = array[3] = 8，key>array[j] ，不进入for循环，最后的array[j+1] =key，即自己和自己本身的值交换，
数组变为***[4，6，7，8，9]***

排序结束！

insertionSortTwo

这个方法比较容易理解了，基于比较交换的方式
外层for循环从第一个元素开始，内层for循环也是从当前元素开始逐个与当前元素的前一个元素比较，如果小于前一个元素，即array[j] < array[j-1]，就把两者的值进行交换，直到第二个元素与第一个元素比较完毕，跳出内部for循环，开始下一个元素的往前比较和交换的排序过程。
还是用**[7，6，8，4，9]**分析

  for (int i = 0; i < array.length; i++) {
            // 将当前元素与已排序的元素逐个比较，找到正确的位置并插入
            for (int j = i; j > 0; j--) {
                // 如果当前元素小于前一个元素，则交换位置
                if (array[j].compareTo(array[j-1]) < 0) {
                    swap(array, j, j-1);
                } else {
                    // 如果当前元素不小于前一个元素，则停止比较
                    break;
                }
            }
        }

第一层外部for循环
i = 0，j = i = 0，不满足内部for循环j>0的要求，即j最小为1，才能进行比较，第二个元素和第一个元素比较，第一个元素没有可以往前比较的元素了。
数组为 [7，6，8，4，9]

第二次外部for循环
i = 1，进入内部for循环，j = i = 1>0，此时array[j] = array[1] = 6，array[j-1] = array[0] = 7，6<7满足if条件，交换j和j-1的元素，j–变为0，内部for循环跳出，
数组为 [6，7，8，4，9]

第三次外部for循环
i = 2，进入内部for循环，j = i = 2>0，此时array[j] = array[2] = 8，array[j-1] = array[1] = 7，8>7不满足if条件，直接break跳出内部for循环
数组为 [6，7，8，4，9]

第四次外部for循环
i = 3，进入内部for循环，j = i = 3>0，此时array[j] = array[3] = 4，array[j-1] = array[2] = 8，4<8满足if条件，交换
array[j] 和 array[j-1]元素，数组变为 [6，7，4，8，9]，j- -变为2>0，继续内部循环
此时array[j] = array[2] = 4，array[j-1] = array[1] = 7，4<7满足if条件，交换array[j] 和 array[j-1]元素，数组变为
[6，4，7，8，9]，j- - 变为1>0，继续内部循环，此时array[j] = array[1] = 4，array[j-1] = array[0] = 6，4<6满足if条件，交换array[j] 和 array[j-1]元素，数组变为 [4，6，7，8，9]，j- - 变为0，跳出for循环，所以本轮for循环结束
数组为 [4，6，7，8，9]

第五次外部for循环
i = 4，进入内部for循环，j = i = 4>0，此时array[j] = array[4] = 9，array[j-1] = array[3] = 8，9>8不满足if条件，直接break跳出内部for循环
数组为 [4，6，7，8，9]

排序结束！

三、总结

两种方式都各有优势，第一种代码更简洁一点，但是空间复杂度稍微高点。
第二种空间复杂度低，逻辑容易理解，但是代码较为复杂，第二种和冒泡排序很像，笔者任务是一样的逻辑，只不过二者顺序相反。同样是从小到大排序的话，插入排序是把小的元素往前排，冒泡是把大的元素往后排，二者的时间复杂度也是一样的。不过笔者的上述代码有个瑕疵，i < array.length这个每次for循环都要判断下，可以在for循环前int length = array.length，i<length更好，时间太晚了，懒得换了。。。休息

熊出没