插入排序算法

​

文章目录

1. 算法思想
2. 算法图解
3. 代码实现
4. 算法特点
5. 算法思想

1. 算法图解

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

至此排序完成

1. 代码实现

代码：

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));
}

}

1. 算法特点

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

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

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

​