插入排序（java 实现）

复习算法之插入排序

插入排序的思想很直接，就是将待排序的数据直接插入到已经排序好的数据列中，实现排序。

实现步骤

1、一个数据为有序，从第二个数据开始比较，插入。
2、第二个数据开始，依次与之前已经排序好的数据，进行比较交换，因为刚开始已经排序的数据就只有一个，因此与第一个数据比较交换。
3、已经排序的数据有两个，插入第三个数据需要与前两个数据依次比较，决定插入位置，对已经排列的数据从右向左依次和待插入的数据进行比较，确定插入位置，直至将待排列数据插入正确位置。
4、重复进行2、3步骤，直到所有数据有序。

package com.lx.sort.algorithm;

import java.util.Arrays;

/**
 * @author lxclk
 * @date 2022/4/21
 */
public class InsertionSort {

    public void insertionSort(int[] arr){
        int count=arr.length;
        for (int i=1;i<count;i++){
            int temp=arr[i];   //保存当前需要插入的数据
            for (int j=i;j>0;j--){
                if (arr[j]<arr[j-1]){
                    arr[j]=arr[j-1];  //依次与较大数据进行交换
                    arr[j-1]=temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        InsertionSort sort=new InsertionSort();
        int[] arr=new int[]{1,3,5,2,3,6,78,5,4,32,4};
        sort.insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }


}

插入排序使用双重循环，平均时间复杂度也是 O(n^2)，使用额外空间进行交换，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。
最优情况，当数据是有序的，只需当前数跟前一个数比较即可，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。