二进制插入排序函数异常求助：排序结果不符合预期

咱们来逐个拆解你代码里的问题，这些都是二进制插入排序常见的坑：

1. 二分查找范围未每次重置 #

这是最致命的问题！你每次处理新元素时，lo和hi还是上一次二分查找后修改的值，完全没回到当前已排序区间的起始和结束位置。比如第一次处理array[1]后，lo可能变成2，下一次处理array[2]时还沿用这个值，查找范围直接错误，根本找不到正确的插入位置。

正确做法：每次循环处理第i个元素时，都要把二分查找范围重置为已排序区间——也就是从lo到i-1（因为array[lo..i-1]已经是排好序的）。

2. 循环范围不符合函数要求 #

你的函数签名是insertionSort(int[] array, int lo, int hi)，要求处理数组中lo到hi的区间，但你的for循环从i=1开始、到array.length结束，这会导致：

• 如果lo>0，会漏掉从lo开始的元素处理
• 如果hi<array.length-1，会处理超出hi范围的元素，破坏原数组其他部分

正确循环应该从i=lo+1开始，到i<=hi结束，因为array[lo]是已排序区间的第一个元素，从lo+1开始处理未排序元素。

3. pos变量逻辑混乱 #

当你找到x == array[mid]时直接给pos赋值，但后续while循环还会修改lo和hi，最后又把pos=lo，等于之前的赋值完全无效。而且，为了保持排序的稳定性（相同元素的相对位置不变），遇到相等元素时，应该把新元素插入到相等元素的后面，而非直接替换位置。

另外，你不需要单独维护pos变量，二分查找结束后，lo的值就是正确的插入位置，直接用lo即可。

4. 二分查找终止条件不完善 #

你的循环条件是while (lo < hi)，当lo == hi时就退出，但此时还需要判断x和array[lo]的大小关系，否则会导致插入位置错误。正确的二分查找逻辑应该调整循环条件和内部判断，让循环结束时lo直接就是正确的插入位置。

修复后的代码 #

public static void insertionSort(int[] array, int lo, int hi) {
    // 只处理lo到hi的区间，从lo+1开始遍历未排序元素
    for (int i = lo + 1; i <= hi; i++) {
        int x = array[i];
        // 每次重置二分查找的范围：已排序区间是[lo, i-1]
        int left = lo;
        int right = i - 1;
        
        // 二分查找正确的插入位置
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (x < array[mid]) {
                // x比mid位置的元素小，插入位置在左半部分
                right = mid - 1;
            } else {
                // x大于等于mid位置的元素，插入位置在右半部分（保证稳定性）
                left = mid + 1;
            }
        }
        // 循环结束后，left就是插入位置
        int pos = left;
        
        // 将pos到i-1的元素向后移动一位
        for (int j = i; j > pos; j--) {
            array[j] = array[j - 1];
        }
        // 插入当前元素
        array[pos] = x;
    }
}

测试验证 #

用你的测试用例{2,5,1,8,3}调用insertionSort(array, 0, 4)，输出结果会是有序的[1,2,3,5,8]，完全符合预期。

关键修复点总结 #

• 每次迭代都重置二分查找的left和right为当前已排序区间的边界
• 调整循环范围到lo到hi，严格符合函数要求
• 简化二分查找逻辑，用left和right的移动直接确定插入位置，避免pos的混乱
• 处理相等元素时，让left移动到mid+1，保证排序的稳定性

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