插入排序（Insertion Sort）

一、算法概述

1.1 算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。

• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

1.2 算法复杂度

1.3 相关概念

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

二、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

2.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

2.2 动图演示

2.3 排序过程

下面选取直接插入排序的一个中间过程对其进行说明。假设{20,30,40,10,60,50}中的前3个数已经排列过，是有序的了；接下来对10进行排列。示意图如下：

图中将数列分为有序区和无序区。我们需要做的工作只有两个：(1)取出无序区中的第1个数，并找出它在有序区对应的位置。(2)将无序区的数据插入到有序区；若有必要的话，则对有序区中的相关数据进行移位。

2.4 代码实现

/**
 * @author: huangyibo
 * @Date: 2021/11/17 16:37
 * @Description: 插入排序
 * 文字描述(以升序为例)
 * 1、将数组分为两个区域, 排序区域和未排序区域, 每一轮从未排序区域中取出第一个元素,　插入到排序区域（需保证顺序）
 * 2、重复以上步骤, 直到整个数组有序
 *
 * 优化方式:
 * 1、待插入元素进行比较时, 遇到比自己小的元素, 就代表找到了插入位置, 无需进行后续比较
 * 2、插入时可直接移动元素, 而不是交换元素
 *
 * 与选择排序比较:
 * 1、二者平均时间复杂度都是O(n²)
 * 2、大部分情况下, 插入都略优于选择
 * 3、有序集合插入的时间复杂度为O(n)
 * 4、插入属于稳定排序算法, 而选择属于不稳定排序算法
 */
public class InsertionSort {

    public static void main(String[] args) {
        int[] arr = {5, 9, 7, 4, 1, 3, 2, 8};

        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        //i代表待插入元素的索引
        for (int i = 1; i < arr.length; i++) {
            //代表待插入的元素值
            int temp = arr[i];
            //j 代表已排序区域的元素索引
            int j = i - 1;
            while (j >= 0){
                if(temp < arr[j]){
                    arr[j + 1] = arr[j];
                }else {
                    //退出循环，减少比较次数
                    break;
                }
                j--;
            }
            //每轮循环后, 将待排序元素插入数组中
            arr[j + 1] = temp;
        }
    }
}

2.5 泛型代码实现

public class InsertionSort {

    public static void main(String[] args) {
        Integer[] arr = {5, 9, 7, 4, 1, 3, 2, 8};

        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static <E extends Comparable<E>> void insertionSort(E[] arr){
        //i代表待插入元素的索引
        for (int i = 1; i < arr.length; i++) {
            //代表待插入的元素值
            E temp = arr[i];
            //j 代表已排序区域的元素索引
            int j = i - 1;
            while (j >= 0){
                if(temp.compareTo(arr[j]) < 0){
                    arr[j + 1] = arr[j];
                }else{
                    //退出循环，减少比较次数
                    break;
                }
                j--;
            }
            //每轮循环后, 将待排序元素插入数组中
            arr[j + 1] = temp;
        }
    }

    public static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2.6 常规双层for循环泛型代码实现

public class InsertionSort {

    public static void main(String[] args) {
        Integer[] arr = {5, 9, 7, 4, 1, 3, 2, 8};

        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static <E extends Comparable<E>> void insertionSort(E[] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if(arr[j].compareTo(arr[j - 1]) < 0){
                    //将arr[j]插到合适的位置
                    swap(arr, j, j - 1);
                }else {
                    break;
                }
            }
        }
    }

    public static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2.7 常规双层for循环泛型代码实现(优化版)

public class InsertionSort {

    public static void main(String[] args) {
        Integer[] arr = {5, 9, 7, 4, 1, 3, 2, 8};

        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static <E extends Comparable<E>> void insertionSort(E[] arr){
        //i代表待插入元素的索引
        for (int i = 1; i < arr.length; i++) {
            //代表待插入的元素值
            E temp = arr[i];
            //j 代表已排序区域的元素索引
            int j;
            for (j = i; j > 0; j--) {
                if(temp.compareTo(arr[j - 1]) < 0){
                    //将arr[j]插到合适的位置
                    arr[j] = arr[j - 1];
                }else {
                    //退出循环，减少比较次数
                    break;
                }
            }
            arr[j] = temp;
        }
    }
}

2.8 算法分析

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

与选择排序比较

• 1、二者平均时间复杂度都是O(n²)
• 2、大部分情况下, 插入都略优于选择
• 3、有序集合插入的时间复杂度为O(n)
• 4、插入属于稳定排序算法, 而选择属于不稳定排序算法

参考： https://www.cnblogs.com/onepixel/articles/7674659.html

https://www.cnblogs.com/skywang12345/p/3596881.html