插入排序实现咨询：代码补全及性能优化方案探讨

嘿，我来帮你搞定这段插入排序的问题～先看代码里的缺失部分，再聊聊怎么优化它的效率。

一、找到缺失的核心代码 #

你这段代码的逻辑框架是对的：把data[i]作为pivot，然后把前面有序区间里比pivot大的元素都右移，但最后忘了把pivot放到它该去的位置！

内层循环结束后，j的位置要么是第一个小于等于pivot的元素索引，要么是-1（说明所有前面的元素都比pivot大），这时候j+1就是pivot的正确插入位置。所以必须在第二个for循环结束后加一行：

data[j+1] = pivot;

修复后的完整sort方法长这样：

public static void sort(int[] data) {
    int j, pivot;
    // 从第2个元素开始，把它插入前面的有序区间
    for (int i = 1; i < data.length; i++) {
        pivot = data[i];
        // 把比pivot大的元素都右移一位
        for (j = i - 1; j >= 0 && data[j] > pivot; j--)
            data[j+1] = data[j];
        // 把pivot放到正确位置——这就是你缺失的步骤！
        data[j+1] = pivot;
    }
}

二、提升插入排序效率的优化方法 #

插入排序本身是O(n²)的算法，但针对不同场景，我们可以做不少优化：

1. 二分查找优化（减少比较次数） #

因为前面的0~i-1区间是有序的，我们不用逐个元素比较找插入位置，用二分查找能直接定位到插入点，减少比较的次数（不过移动元素的次数还是一样，适合比较成本高的场景）。

优化后的代码示例：

public static void binaryInsertionSort(int[] data) {
    int pivot, left, right, mid;
    for (int i = 1; i < data.length; i++) {
        pivot = data[i];
        left = 0;
        right = i - 1;
        // 二分查找找插入位置
        while (left <= right) {
            mid = (left + right) / 2;
            if (pivot < data[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 把left到i-1的元素右移，给pivot腾位置
        for (int j = i - 1; j >= left; j--) {
            data[j+1] = data[j];
        }
        // 插入pivot
        data[left] = pivot;
    }
}

2. 希尔排序（分组插入，大幅降低移动成本） #

这是插入排序的“进阶版”，核心思路是先把数组按增量gap分成多个子序列，分别做插入排序，然后逐步缩小gap直到为1。这样数组会越来越接近有序，最后一次普通插入排序的效率会极高，整体时间复杂度能降到O(n^1.3)左右，适合中等规模的无序数组。

简单实现示例：

public static void shellSort(int[] data) {
    int n = data.length;
    // 初始gap取数组长度的一半，每次减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个子序列做插入排序
        for (int i = gap; i < n; i++) {
            int pivot = data[i];
            int j;
            // 子序列内的元素间隔为gap
            for (j = i; j >= gap && data[j - gap] > pivot; j -= gap) {
                data[j] = data[j - gap];
            }
            data[j] = pivot;
        }
    }
}

3. 提前终止优化（针对接近有序的数组） #

如果当前pivot已经比前一个元素大，说明它本来就在正确的位置，完全不用做后续的移动操作，直接跳过当前循环就行。这个优化在数组接近有序时，能大幅减少不必要的操作。

代码示例：

public static void optimizedInsertionSort(int[] data) {
    int j, pivot;
    for (int i = 1; i < data.length; i++) {
        pivot = data[i];
        // 提前判断：如果pivot比前一个元素大，直接跳过
        if (pivot >= data[i-1]) {
            continue;
        }
        // 否则再做移动和插入
        for (j = i - 1; j >= 0 && data[j] > pivot; j--)
            data[j+1] = data[j];
        data[j+1] = pivot;
    }
}

内容的提问来源于stack exchange，提问作者ccc8763