递归实现Binary Insertion Sort：部分数组正常部分触发StackOverflow问题排查

核心问题分析 #

你的代码在处理{3,7,2,4}时触发栈溢出，主要由以下几个错误导致：

• 缺少无效查找范围的终止条件：当LeftPointer > RightPointer时，说明已确定插入位置，但代码未处理该情况，导致递归无法终止，最终引发栈溢出。例如插入元素2时，RightPointer会被设为-1，此时LeftPointer(0) > RightPointer(-1)，代码仍继续执行判断并递归，陷入死循环。
• 未处理元素相等的场景：当a[i] == a[MiddlePointer]时，三个条件分支都不匹配，直接返回但未终止递归，可能导致上层调用重复触发递归。
• 值类型参数传递的误区：C#中LeftPointer、RightPointer、MiddlePointer是值类型，Testing方法内修改这些参数不会反馈到上层调用，导致递归过程中指针无法正确更新，加剧无限递归的风险。
• 移位逻辑错误：Testing方法中的移位循环j>0应改为j>LeftPointer，否则会错误移动整个数组的元素，而非仅已排序区间内的元素。

修复后的代码 #

int[] a = new int[] { 3, 7, 2, 4 }; // 待排序数组
int i = 1; // 第一个元素默认已排序，从第二个元素开始处理

BinaryInsertSort(a, i);

void BinaryInsertSort(int[] a, int i)
{
    if (i == a.Length)
        return;

    // 已排序区间为[0, i-1]，递归查找当前元素的插入位置
    int insertPos = BinarySearchInsertPos(a, 0, i - 1, a[i]);
    
    // 将插入位置后的已排序元素右移，腾出插入空间
    int temp = a[i];
    for (int j = i; j > insertPos; j--)
    {
        a[j] = a[j - 1];
    }
    a[insertPos] = temp;

    // 递归处理下一个元素
    BinaryInsertSort(a, i + 1);
}

int BinarySearchInsertPos(int[] a, int left, int right, int target)
{
    // 终止条件：查找范围失效，返回left作为插入位置
    if (left > right)
        return left;

    int mid = (left + right) / 2;
    
    if (target < a[mid])
        return BinarySearchInsertPos(a, left, mid - 1, target);
    else if (target > a[mid])
        return BinarySearchInsertPos(a, mid + 1, right, target);
    else
        // 元素相等时返回mid位置（若需稳定排序可返回mid+1）
        return mid;
}

修复说明 #

• 拆分递归职责：将二分查找与插入逻辑分离，BinaryInsertSort负责迭代处理每个元素，BinarySearchInsertPos专注于递归查找插入位置，结构更清晰。
• 添加终止条件：当left > right时直接返回插入位置，彻底避免无限递归。
• 处理元素相等场景：明确目标元素等于中间元素时的插入位置，保证逻辑完整性。
• 修正移位逻辑：仅移动已排序区间内的元素，避免不必要的数组操作。
• 规避值传递问题：通过返回插入位置的方式，代替修改值类型参数，确保上层调用能获取正确的位置信息。

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