插入排序

算法定义

插入排序（Insertion Sort）是一种简单直观的排序算法，它的核心思想是将数组分为 “已排序” 和 “未排序” 两部分，每次从 “未排序” 部分取出一个元素，插入到 “已排序” 部分的合适位置，直到所有元素都被插入完毕。

这种排序方式类似于人们整理扑克牌的过程 —— 每次拿起一张牌，将其插入到手中已有序的牌组中的正确位置。

算法思路

插入排序的具体步骤如下：

初始时，将数组的第一个元素视为 “已排序” 部分（只有一个元素的数组天然有序）。
从第二个元素开始，依次取出 “未排序” 部分的元素，将其与 “已排序” 部分的元素从后向前比较。
如果 “已排序” 部分的元素大于当前待插入元素，则将该元素后移一位。
找到合适的插入位置后，将待插入元素放入该位置。
重复步骤 2-4，直到所有元素都被插入到 “已排序” 部分。

算法复杂度

最好时间复杂度：O (n) - 当数组已经有序时，只需遍历一次，无需移动元素
最坏时间复杂度：O (n²) - 当数组完全逆序时，每个元素都需要移动到最前面
平均时间复杂度：O(n²)
空间复杂度：O (1) - 只需一个临时变量存储待插入元素，属于原地排序

优点与缺点

优点：
- 实现简单，代码简洁易懂
- 原地排序，空间复杂度低（O (1)）
- 稳定的排序算法（相等元素的相对位置保持不变）
- 对几乎有序的数组或小规模数据效率很高
- 适合增量排序（可以高效处理动态新增的数据）
缺点：
- 时间复杂度为 O (n²)，不适合大规模数据排序
- 元素移动次数较多（最坏情况下需要 O (n²) 次移动）
- 对逆序数组处理效率低

应用场景

小规模数据的排序（如长度小于 100 的数组）
几乎有序的数组（此时效率接近 O (n)）
作为复杂排序算法的子过程（如快速排序处理小规模子数组时）
数据流式输入的场景（可以边接收数据边排序）
链表排序（插入操作无需移动元素，只需修改指针）

各版本优化说明

基本版：
- 最直观的实现，依次将元素插入到已排序部分的正确位置
- 逻辑清晰，但比较和移动次数较多
减少交换次数优化：
- 基本版的改进版，将多次交换操作改为一次赋值
- 通过先暂存待插入元素，再将大于它的元素后移，最后插入
- 减少了一半的数据移动操作，性能有所提升
二分查找优化：
- 用二分查找代替线性查找来确定插入位置，将比较次数从 O (n) 降至 O (log n)
- 适合数据量较大的情况，但元素移动次数仍为 O (n)
- 总体时间复杂度仍为 O (n²)，但常数因子更小
希尔排序（分组插入排序）：
- 插入排序的重大改进，通过分组（按步长 gap）进行插入排序
- 先让数组整体基本有序，最后再进行一次普通插入排序
- 时间复杂度可提升至 O (n^1.3) 左右，适合中等规模数据

插入排序是一种非常实用的排序算法，尤其是在处理小规模数据或几乎有序的数据时表现出色。许多编程语言的标准库中，在处理小规模子数组时都会选择插入排序（如 Java 的Arrays.sort()）。

代码

import java.util.Arrays;

public class InsertionSort {
    
    // 1. 基本版插入排序
    public static void insertionSortBasic(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        // 从第二个元素开始遍历未排序部分
        for (int i = 1; i < n; i++) {
            int key = arr[i]; // 当前待插入元素
            int j = i - 1;    // 已排序部分的最后一个元素索引
            
            // 从后向前比较已排序部分，找到插入位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j]; // 元素后移
                j--;
            }
            arr[j + 1] = key; // 插入元素
        }
    }
    
    // 2. 优化版1：减少元素交换次数（使用赋值代替交换）
    public static void insertionSortOptimized1(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        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--;
            }
            arr[j + 1] = key;
        }
    }
    
    // 3. 优化版2：二分查找优化（减少比较次数）
    public static void insertionSortBinarySearch(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        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 (key < arr[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            // 将插入位置后的元素后移
            for (int j = i - 1; j >= left; j--) {
                arr[j + 1] = arr[j];
            }
            arr[left] = key; // 插入元素
        }
    }
    
    // 4. 优化版3：希尔排序（分组插入排序）
    public static void shellSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        
        int n = arr.length;
        // 初始步长设为数组长度的一半，逐渐减小
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个子数组进行插入排序
            for (int i = gap; i < n; i++) {
                int key = arr[i];
                int j = i;
                
                // 对以gap为步长的子数组进行插入排序
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90, 5};
        int[] arr1 = Arrays.copyOf(arr, arr.length);
        int[] arr2 = Arrays.copyOf(arr, arr.length);
        int[] arr3 = Arrays.copyOf(arr, arr.length);
        int[] arr4 = Arrays.copyOf(arr, arr.length);
        
        insertionSortBasic(arr1);
        System.out.println("基本版: " + Arrays.toString(arr1));
        
        insertionSortOptimized1(arr2);
        System.out.println("减少交换优化: " + Arrays.toString(arr2));
        
        insertionSortBinarySearch(arr3);
        System.out.println("二分查找优化: " + Arrays.toString(arr3));
        
        shellSort(arr4);
        System.out.println("希尔排序（分组优化）: " + Arrays.toString(arr4));
    }
}