插入排序算法

作者：敲代码の流川枫

博客主页：流川枫的博客

专栏：和我一起学java

语录：Stay hungry stay foolish

工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网

点击免费注册和我一起刷题吧

1. 算法思想

插入排序的主要思想就是，对于未排序的数据，在已排序的序列从后向前扫描，找到相应的位置并插入

既然插入到序列中了，就要给它腾出空间来，我们需要将插入位置之后的已排序元素像右移动一位

插入排序所需要的时间取决于数据的原始顺序，当对部分有序的数据使用插入排序十分高效

2. 算法图解

int[] array = {4,5,2,6,8,7};

以数组array为例分析

for 循环开始，直到i=1,即preIndex=1

45是有序的，preIndex指向5，currentValue指向2，2小于5并且小于4，将两个元素分别后移一位，并且preIndex自减两次为-1，此时找到插入的位置为preIndex+1，即0位置插入2

循环继续，preIndex指向8，currentValue指向7，7小于8，将8后移一位，并且preIndex自减一次为3，找到插入的位置为preIndex+1，即4位置插入7

至此排序完成

3. 代码实现

代码：

import java.util.Arrays;
public class InsertionSort {
    public int[] sortArray(int[] nums){
        if(nums.length==0){
            return nums;
        }
        int currentValue;//存放当前值，当前值前的数据已经有序
        for (int i = 0; i < nums.length-1; i++) {
            int preIndex = i;//已被排序的数据的索引
            currentValue = nums[preIndex + 1];
            //在已排序的数据中倒序寻找比当前数据小的数据，将其后移一位
            while(preIndex>=0 && currentValue < nums[preIndex]){
                nums[preIndex+1] = nums[preIndex];
                preIndex--;
            }
            //程序走到这里，已经找到合适的插入位置，将当前数据插入
            nums[preIndex+1] = currentValue;
            System.out.println("本轮插入后的数组");
            System.out.println(Arrays.toString(nums));
        }
        return nums;
    }

    public static void main(String[] args) {
        int nums[] = {3,4,5,2,1,6,10,8};
        InsertionSort insertionSort = new InsertionSort();
        insertionSort.sortArray(nums);
        System.out.println("排序结束");
        System.out.println(Arrays.toString(nums));
    }
}

运行结果：

4. 算法特点

特点：稳定，相对顺序不会变，在序列基本有序的情况下，排序时间短；最差的情况应该是将序列倒序变成顺序

适用场景：数据基本有序，小数组，要求稳定

时间复杂度：最坏情况下为O(N2)，此时待排序列为逆序，或者说接近逆序
      最好情况下为O(N)，此时待排序列为升序，或者说接近升序
空间复杂度：O(1)

“ 本期的分享就到这里了， 记得给博主一个三连哈，你的支持是我创作的最大动力！