插入排序算法（基于Java实现）

2020-12-15

字数统计: 1.3k字 | 阅读时长≈ 5分

插入排序算法（基于Java实现）

插入排序算法原理及代码实现：

一、插入排序算法的原理

首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

如图所示，要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。

对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。

为什么说移动次数就等于逆序度呢？我拿刚才的例子画了一个图表，你一看就明白了。满有序度是 n*(n-1)/2=15，初始序列的有序度是 5，所以逆序度是 10。插入排序中，数据移动的个数总和也等于 10=3+3+4。

二、插入排序算法的代码实现

package com.company;

import java.util.Arrays;

public class InsertionSort {
  
    public static int[] insertionSort(int[] a){
        if(a.length<=1) return a;
        for(int i = 1; i<a.length; ++i){
            int value = a[i];
            int j = i-1;
            //查找插入的位置
            for(; j >= 0; --j){
                if(a[j] > value){
                    a[j+1] = a[j];
                }else{
                    break;
                }
            }
            a[j+1] = value;
        }
        return a;
    }

    public static void main(String[] args) {
        int[] a = {10, 9, 7, 4, 3, 2, 1, 8};
        System.out.println("之前的排序：");
        System.out.println(Arrays.toString(a));

        insertionSort(a);
        System.out.println("之后的排序：");
        System.out.println(Arrays.toString(a));
    }
}

输出的结果：

之前的排序：
[10, 9, 7, 4, 3, 2, 1, 8]
之后的排序：
[1, 2, 3, 4, 7, 8, 9, 10]

插入排序算法另一种写法，即算法改进：

package TestSort;

import java.util.Arrays;

public class Test_InsertSort {
    public static void InsertSort(int[] arr){
        int insertVal = 0;
        int insertIndex = 0;
        for(int i = 1; i < arr.length; i++){
            //定义待插入的数
            insertVal = arr[i];
            insertIndex = i - 1;//待插入数前面数的下标

            //给insertVal找到插入的位置
            //insertIndex >= 0是保证给insertVal找到插入位置时，不越界
            //insertVal < arr[insertIndex] 如果符合该判断，就说明还没有找到插入位置，就需要将arr[insertIndex]后移
            while(insertIndex >= 0 && insertVal < arr[insertIndex]){
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            //当退出while循环时，说明插入的位置已经找到，insertIndex + 1
            if(insertIndex + 1 != i){
                arr[insertIndex + 1] = insertVal;
            }
        }

    }

    public static void main(String[] args) {
        int[] arr = {23, 43, 3, 32, 67, 78, 34, 56};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));

        InsertSort(arr);

        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }

}

输出结果为：

排序前：
[23, 43, 3, 32, 67, 78, 34, 56]
排序后：
[3, 23, 32, 34, 43, 56, 67, 78]

从上述的代码实现过程中，可以明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度为O(1)**，也就是，这是一个原地排序算法**。

在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数组里面查找插入位置，每次只需要比较一个数据就能够确定插入的位置。所以在这种情况下，**最好的时间复杂度为O(n)**。注意，这里是从尾到头遍历已经有序的数据。

如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以**最坏情况时间复杂度为 O(n^2)**。

还记得我们在数组中插入一个数据的平均时间复杂度是多少吗？没错，是 O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以**平均时间复杂度为 O(n2)**。

本文作者： feng之锋
本文链接： http://example.com/2020/12/15/插入排序算法/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！