排序算法—插入排序（插入、希尔）（动图演示）

1.初始化：

将数组的第一个元素（arr[0]）视为已排序部分。
其余部分（arr[1]到arr[n-1]）视为未排序部分。

2.遍历未排序部分：

从i=1到n-1（n为数组长度)，依次取出arr[i]作为待插入元素key。

3.从右向左比较并移动元素：

初始化j=i－1（即已排序部分的最后一个元素)。
如果 arr[j］> key，则arr[j]向后移动一位（arr[j+1] = arr[j]），并继续向左比较（j--）
直到找到arr[j] ≤ key或j<0（即已比较完所有已排序元素)。

4.插入key到正确位置：

将key 插入到arr[j+1]的位置。

5.重复上述过程，直到所有未排序元素都被处理。

优化方式：

二分查找优化（Binary Insertion Sort）

优化思路：在已排序部分使用二分查找快速找到插入位置，减少比较次数（但仍需移动元素）。

终止条件：

外层循环终止：当所有未排序元素（i 从 1 到 n-1）都被处理完毕时，排序结束。

内层循环终止：

当 j < 0（即已比较完所有已排序元素）。

或 arr[j] ≤ key（找到正确插入位置）。

动图演示：

性能分析：

时间复杂度：

情况时间复杂度说明
最优情况（已排序数组） O(n)O(n) 每次只需比较一次，无需移动元素
最坏情况（完全逆序） O(n2)O(n2) 每次插入需比较和移动所有已排序元素
平均情况（随机数组） O(n2)O(n2) 平均需要 n2/4n2/4 次比较和移动

空间复杂度：

空间复杂度：需常数额外空间O(1)。

稳定性：

稳定

情况	时间复杂度	说明
最优情况（已排序数组）	O(n)O(n)	每次只需比较一次，无需移动元素
最坏情况（完全逆序）	O(n2)O(n2)	每次插入需比较和移动所有已排序元素
平均情况（随机数组）	O(n2)O(n2)	平均需要 n2/4n2/4 次比较和移动

代码实现（Java）：

public static void insertionSort(int[] arr) {
    // 边界检查：如果数组为空或长度小于等于1，直接返回
    if (arr == null || arr.length <= 1) {
        return;
    }
    
    // 外层循环：遍历未排序部分(从第二个元素开始)
    for (int i = 1; i < arr.length; i++) {
        // 保存当前需要插入的元素值
        int key = arr[i];
        // 初始化比较指针，指向已排序部分的最后一个元素
        int j = i - 1;
        
        // 内层循环：在已排序部分中寻找合适的插入位置
        // 从后向前比较，同时移动大于key的元素
        while (j >= 0 && arr[j] > key) {
            // 将大于key的元素向后移动一位
            arr[j + 1] = arr[j];
            // 继续向前比较
            j--;
        }
        
        // 将key插入到正确位置
        arr[j + 1] = key;
    }
}

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

算法步骤：

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序
主要思想就是，先进行两两比较，如果是升序，就先将小的数换到左边，大的换到右边。

直到gap等于1时，就回到了直接插入排序。（这里的gap可以自己设定，只需最后等于1即可）此时进行直接插入排序时效率会提升不少。

动图演示：

性能分析：

时间复杂度：

本实现的gap/3+1序列平均性能优于传统n/2序列

最坏情况仍为O(n²)，但实际运行中很少出现

当数据部分有序时，性能接近O(n log n)

空间复杂度：

仅使用常数个临时变量 O(1)

稳定性：

不稳定

代码实现（Java）：

这里使用的优化方法：每次除以3的收敛速度优于除以2。

public static void shellSort(int[] arr) {
    // 边界检查：如果数组为空或长度小于2，直接返回
    if (arr == null || arr.length < 2) {
        return;
    }

    int n = arr.length;
    int gap = n;  // 初始化间隔（gap）为数组长度
    
    // 外层循环：动态计算并更新间隔（gap）
    // 使用 gap = gap / 3 + 1 的增量序列：
    // 1. 除以3比传统除以2能更快缩小间隔
    // 2. +1 保证最终gap=1时能完成最后一次标准插入排序
    while (gap > 1) {
        gap = gap / 3 + 1;  // 计算新的间隔
        
        // 中层循环：从gap位置开始，对每个元素进行组内插入排序
        // 这里i++（而不是i+=gap）是因为要轮流处理各个分组
        for (int i = gap; i < n; i++) {
            int temp = arr[i];  // 当前待插入元素
            int j = i - gap;   // 指向同组前一个元素
            
            // 内层循环：在同组内进行插入排序
            // 将大于temp的元素向后移动gap位
            while (j >= 0 && arr[j] > temp) {
                arr[j + gap] = arr[j];  // 大元素后移
                j -= gap;              // 继续检查组内前一个元素
            }
            
            // 将temp插入到正确位置
            // 注意：此时j可能为-gap（需要插入到组首）
            arr[j + gap] = temp;
        }
        
        // 调试时可打印每轮排序结果：
        // System.out.println("gap=" + gap + ": " + Arrays.toString(arr));
    }
}