直接插入排序

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            int key = arr[i]; // 当前待插入元素
            int j = i - 1;
            
            // 将大于key的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            
            // 找到key的正确位置，插入
            arr[j + 1] = key;
        }
    }
    

    //直接插入排序
    public static void insertSort(int[] array) {
        //i下标从数组的第二个值开始
        for (int i = 1; i < array.length ; i++) {
            int tmp = array[i];//tmp存放i下标的值
            int j = i - 1;//j下标为i的前一个位置
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    //j下标的值大，将j下标的值放到j的下一个位置
                    array[j + 1] = array[j];
                }else {
                    //j下标的值较小，j小标的值要直接放到j的下一个位置
                   break;
                }
            }
            //此时j下标的值是负数了，将tmp的值放到j变量的后一个位置
            array[j + 1] = tmp;
        }
    }

二分查找优化

在原来的基础上，可以使用二分查找来加速寻找插入位置的过程，减少比较次数：

public static void binaryInsertionSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int left = 0;
        int right = i - 1;
        
        // 使用二分查找找到插入位置
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // 将元素后移
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        
        // 插入元素
        arr[left] = key;
    }
}

优缺点

优点

• 算法实现简单，容易理解
• 对于小规模数据或基本有序的数据效率较高
• 稳定的排序算法
• 适合增量式排序（可以一边插入元素一边保持有序）
• 对于接近有序的数组，时间复杂度接近O(n)

缺点

• 对于大规模乱序数组，时间复杂度为O(n²)，效率较低
• 需要较多的元素移动操作
• 不适合对倒序或接近倒序的数组进行排序

应用场景

• 数据规模较小的排序任务
• 对几乎已经排好序的数据进行排序
• 在线算法场景：数据是实时到达的，需要动态地将新元素插入到已排序的序列中
• 嵌入式系统或资源受限环境
• 作为更复杂排序算法（如希尔排序）的基础