请求排查C# QuickSort算法的StackOverflowException问题

嘿，我太懂这种写好算法却遇到栈溢出崩溃的挫败感了！之前我写快速排序的时候也踩过一模一样的坑，给你梳理下最常见的几个原因和解决办法：

最可能的元凶：递归终止条件缺失或错误 #

快速排序的递归必须有明确的终止边界——当beginning >= end时，说明当前子数组只有0个或1个元素，完全不需要再排序。如果你的代码里漏掉了这个判断，就会陷入无限递归，直接把调用栈撑爆。

正确的终止逻辑应该放在方法最开头：

private static void QuickSort(int[] numbers, int beginning, int end)
{
    // 必须先加这个终止判断！
    if (beginning >= end)
        return;
    
    // 后续的分区、递归逻辑...
}

第二大诱因：基准值（Pivot）选择不合理 #

如果每次都选子数组的第一个或最后一个元素当基准值，在数组已经有序或者接近有序的情况下，递归深度会达到O(n)级别，而.NET的默认调用栈容量根本扛不住这么深的递归（比如数组长度超过10000就很容易触发溢出）。

解决办法是优化基准值的选择：

• 三数取中法：选子数组的第一个、中间、最后一个元素的中位数当基准值
• 随机选择基准值

举个三数取中的实现示例：

private static int ChoosePivot(int[] numbers, int beginning, int end)
{
    int mid = beginning + (end - beginning) / 2;
    // 调整三个位置的元素，把中位数放到end位置方便后续分区
    if (numbers[beginning] > numbers[mid])
        Swap(numbers, beginning, mid);
    if (numbers[beginning] > numbers[end])
        Swap(numbers, beginning, end);
    if (numbers[mid] > numbers[end])
        Swap(numbers, mid, end);
    return numbers[end];
}

private static void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

终极备选方案：改成迭代版快速排序 #

如果递归深度的问题始终没法彻底解决，直接把递归逻辑改成用栈模拟的迭代版，完全避开调用栈溢出的问题：

private static void IterativeQuickSort(int[] numbers)
{
    Stack<int> stack = new Stack<int>();
    stack.Push(0);
    stack.Push(numbers.Length - 1);

    while (stack.Count > 0)
    {
        int end = stack.Pop();
        int beginning = stack.Pop();

        if (beginning >= end)
            continue;

        int pivotIndex = Partition(numbers, beginning, end);

        // 把左右子数组的边界压入栈中
        stack.Push(beginning);
        stack.Push(pivotIndex - 1);
        stack.Push(pivotIndex + 1);
        stack.Push(end);
    }
}

// 这里需要你实现对应的分区方法
private static int Partition(int[] numbers, int beginning, int end)
{
    // 你的分区逻辑（比如 Lomuto 或 Hoare 分区法）
}

快速排查小技巧 #

如果还是找不到问题，可以在递归方法开头加一行调试输出，打印每次的beginning和end值，看看是不是出现了beginning > end的异常情况，或者递归深度异常大，这样就能快速定位到问题根源。

内容的提问来源于stack exchange，提问作者J. L.