递归快速排序函数出现无限循环（栈溢出）问题求助

看起来你遇到了快速排序递归实现里的经典坑——栈溢出，这大概率是因为递归没有正确收敛，加上比较逻辑的错误，导致程序陷入无限递归调用。我帮你拆解一下问题，再给出修复方案：

首先梳理核心问题点： #

1. CompareString函数逻辑混乱

   • 你在比较姓氏时，lName1[i] < lName2[i]返回true（表示前者应该排在前面），但比较名字时却写了fName1[j] < fName2[j]返回false，逻辑完全相反！这会导致名字比较的结果颠倒，排序时指针移动完全错误。
   • 没有处理姓氏/名字长度不一致的情况（比如"Smi"和"Smith"），这种情况下直接跳去比较名字是不对的，应该把较短的前缀字符串排在前面。

2. 快速排序的分区与递归逻辑有漏洞

   • 你注释掉了pivot的赋值，而且全程用初始leftInd对应的元素作为基准值，但没有处理pivot的位置调整，导致分区后的边界可能无法缩小，触发无限递归。
   • 移动l和r指针时没有检查数组边界，比如当l递增到超过rightInd时，再访问diverList[l]会直接抛出索引越界错误，这也是你截图里报错的原因之一。
   • 缺少递归终止条件：当leftInd >= rightInd时（区间只有一个或没有元素），应该直接返回，否则会不断递归无效区间。

修复后的代码示例： #

1. 修正CompareString的比较逻辑

统一判断逻辑：返回true表示第一个姓名的字典序小于第二个，应该排在前面。

public bool CompareString(string lName1, string lName2, string fName1, string fName2)
{
    // 先比较姓氏
    int minLastLen = Math.Min(lName1.Length, lName2.Length);
    for (int i = 0; i < minLastLen; i++)
    {
        if (lName1[i] < lName2[i])
            return true;
        else if (lName1[i] > lName2[i])
            return false;
        // 字符相等则继续比较下一个
    }
    // 姓氏是前缀关系，较短的排在前面
    if (lName1.Length != lName2.Length)
    {
        return lName1.Length < lName2.Length;
    }
    // 姓氏相等，比较名字
    int minFirstLen = Math.Min(fName1.Length, fName2.Length);
    for (int j = 0; j < minFirstLen; j++)
    {
        if (fName1[j] < fName2[j])
            return true;
        else if (fName1[j] > fName2[j])
            return false;
    }
    // 名字是前缀关系，较短的排在前面
    return fName1.Length < fName2.Length;
}

2. 修正SortList的递归与分区逻辑

添加递归终止条件，选择中间元素作为pivot（避免最坏时间复杂度），同时增加边界检查防止索引越界：

public void SortList(int leftInd, int rightInd)
{
    // 递归终止：区间无需排序
    if (leftInd >= rightInd)
        return;

    int l = leftInd;
    int r = rightInd;
    // 选中间元素当基准，避免极端情况
    int pivotIdx = (leftInd + rightInd) / 2;
    DiverRec pivot = diverList[pivotIdx];
    string pLast = LastName(pivot.name);
    string pFirst = FirstName(pivot.name);

    while (l <= r)
    {
        // 找左边第一个不小于pivot的元素
        while (l <= rightInd && CompareString(LastName(diverList[l].name), pLast, FirstName(diverList[l].name), pFirst))
        {
            l++;
        }
        // 找右边第一个不大于pivot的元素
        while (r >= leftInd && !CompareString(LastName(diverList[r].name), pLast, FirstName(diverList[r].name), pFirst))
        {
            r--;
        }

        if (l <= r)
        {
            // 交换元素
            DiverRec temp = diverList[l];
            diverList[l] = diverList[r];
            diverList[r] = temp;
            l++;
            r--;
        }
    }

    // 递归排序左右子区间
    SortList(leftInd, r);
    SortList(l, rightInd);
}

3. 增强LastName和FirstName的健壮性

防止输入名字没有空格的情况（比如只有单名），避免索引错误：

public string LastName(string fullName)
{
    int spacePos = fullName.IndexOf(' ');
    // 没有空格则返回整个字符串
    return spacePos == -1 ? fullName : fullName.Substring(spacePos + 1);
}

public string FirstName(string fullName)
{
    int spacePos = fullName.IndexOf(' ');
    // 没有空格则返回整个字符串
    return spacePos == -1 ? fullName : fullName.Substring(0, spacePos);
}

为什么这些修复能解决问题？ #

• 统一的比较逻辑确保排序时指针移动符合预期，不会出现明明应该移动却不动的情况。
• 递归终止条件直接掐断了无效的递归调用，避免无限递归导致栈溢出。
• 选择中间元素作为pivot能减少最坏情况的出现，同时边界检查避免了索引越界错误。

备注：内容来源于stack exchange，提问作者Antonio 1113