直接插入排序逻辑

将数组分为有序和无序两部分，有序在前，无序在后，首先默认数组第一位是一个只有一位数字的有序数组

每次将一个无序的数按有序要求插入有序之中，循环到每个无序都插入有序

因为是依次插入有序数组中，等值的数不会发生位置交换，所以 直接插入排序是稳定排序

复杂度分析

平均时间复杂度：O(n^2)

空间复杂度：O(1)

最差情况的时间复杂度是在输入数组逆序的情况下，此时每次插入都需要将已排序部分中的所有元素后移，时间复杂度为O(n^2)

最好情况的时间复杂度是在输入数组基本有序的情况下，时间复杂度接近O(n)

代码实现

class Main {
    public static void insertSort(int[] arr) {
        if(arr == null || arr.length < 2) return;
        int len = arr.length;
        // i之前的数组有序
        for(int i = 1; i < len; i++) {
            // 每次都将第i位的数 “冒泡”到i之前有序的位置
            for(int j = i - 1; j >= 0 && arr[j] > arr[j+1]; j--) {
                swap(arr, j, j+1);
            }
        }
        return;
    }
    
    // 交换方法，交换数组arr的第n和第m位
    public static void swap(int[] arr, int n, int m) {
        int mid = arr[m];
        arr[m] = arr[n];
        arr[n] = mid;
    }
}

使用场景

  1. 对于小规模的数组，由于直接插入排序的时间复杂度较低，因此效率较高。
  2. 对于基本有序的数组，直接插入排序的性能十分优秀