C++字符串快速排序函数陷入无限循环，求问题排查与修复方案

问题根源 #

你的快排代码陷入无限循环主要有以下几个核心问题：

• 第一个循环无边界且条件错误：while (X[I].Nombre <= PIVOTE) 会让I持续递增，哪怕所有元素都等于PIVOTE，最终I会越界，导致后续逻辑混乱；同时这个循环的目标应该是找到第一个大于PIVOTE的元素，而非小于等于。
• 第二个循环无边界检查：while (X[J].Nombre > PIVOTE) 没有限制J的下限，当所有元素都大于PIVOTE时，J会减到小于数组起始下标，引发未定义行为。
• 交换条件逻辑错误：用X[I].Nombre <= X[J].Nombre作为交换判断依据，可能在I已经超过J的情况下仍执行交换，破坏分区逻辑，导致递归时子区间无法缩小，最终无限递归。

修复方案 #

1. 给两个while循环添加边界限制，防止下标越界；
2. 调整第一个while的条件为X[I].Nombre < PIVOTE，准确找到第一个大于基准值的元素；
3. 将交换条件改为I <= J，确保仅在左右指针未交叉时执行交换；
4. 保留递归的边界判断，确保子区间有效时才递归调用。

修复后完整代码 #

struct Personaslista
{
    std::string Nombre;
    int EspacioArreglo = 0;
} X[CantidadDePersonas];


void QUICKSORT(int Primero, int Ultimo, int B)
{
    int I, J, Central = 0;
    std::string PIVOTE;

    Central = (Primero + Ultimo) / 2;
    PIVOTE = X[Central].Nombre;

    I = Primero;
    J = Ultimo;

    do
    {
        // 找第一个大于PIVOTE的元素，同时限制I不超过Ultimo
        while (I < Ultimo && X[I].Nombre < PIVOTE)
        {
            I++;
        }
        // 找第一个小于等于PIVOTE的元素，同时限制J不小于Primero
        while (J > Primero && X[J].Nombre > PIVOTE)
        {
            J--;
        }

        // 仅当指针未交叉时交换元素
        if (I <= J)
        {
            std::string Temp = X[I].Nombre;
            int Poral = X[I].EspacioArreglo;
            X[I].Nombre = X[J].Nombre;
            X[I].EspacioArreglo = X[J].EspacioArreglo;
            X[J].Nombre = Temp;
            X[J].EspacioArreglo = Poral;
            I++;
            J--;
        }

    } while (I <= J);

    if (Primero < J)
    {
        QUICKSORT(Primero, J, B);
    }

    if (I < Ultimo)
    {
        QUICKSORT(I, Ultimo, B);
    }

    return;
}

额外优化提示 #

• 交换操作可以简化为直接交换整个Personaslista对象，代码更简洁：std::swap(X[I], X[J]);，需要包含<algorithm>头文件；
• 确保CantidadDePersonas是已定义的常量，避免数组大小不确定的问题；
• 基准值选择中间元素的逻辑合理，可避免已排序数组等极端情况导致的快排性能退化。

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