插入排序（Java）

不知名的忻

200人浏览 · 2026-05-14 21:10:24

不知名的忻 · 2026-05-14 21:10:24 发布

插入排序的三个进化阶段：

直接插入排序 → 折半插入排序 → 希尔排序
     ↑              ↑              ↑
  基础版        优化比较次数      突破 O(n²)

而「2路插入排序」是折半插入的一种变体，实际很少用，我最后提一下。

一、直接插入排序（基础）[要求会写代码]

思路：就像打扑克，每来一张新牌，插到前面已经排好序的牌里。

代码：

public void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; 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;
    }
}

复杂度：

最好 O(n)（已经有序）
最坏 O(n²)（倒序）
平均 O(n²)

特点：稳定、小数据量最快、对基本有序的数据友好。

二、折半插入排序

优化点：直接插入排序找插入位置时是「挨个比较」，改成「二分查找」。

代码：

public void binaryInsertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int left = 0, right = i - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] > key) right = mid - 1;
            else left = mid + 1;
        }
        // 此时 left 就是要插入的位置
        for (int j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
    }
}

复杂度：

比较次数 O(n log n)（比直接插入好）
移动次数还是 O(n²)（瓶颈没变）

特点：减少了比较次数，但移动次数没变，整体还是 O(n²)。

三、希尔排序（真正突破 O(n²)）[要求会写代码]

思路：先分组粗排，再整体细排。让数组基本有序后，最后一轮直接插入排序就很快。

代码：


public void shellSort(int[] arr) {
    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;
            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = key;
        }
    }
}

复杂度：

最好 O(n log n)
最坏 O(n²)（但很难达到）
平均 ≈ O(n^1.3) ~ O(n^1.5)

特点：不稳定、突破 O(n²)、是插入排序中的天花板。

四、效率对比（重点）

排序算法	最好	最坏	平均	稳定性	推荐场景
直接插入	O(n)	O(n²)	O(n²)	✅ 稳定	小数据、基本有序
折半插入	O(n log n)	O(n²)	O(n²)	✅ 稳定	和直接插入差不多
希尔排序	O(n log n)	O(n²)	O(n^1.3)	❌ 不稳定	大数据、通用
2路插入	—	O(n²)	O(n²)	✅ 稳定	基本不用