快速排序后缀数组异常排查：首次分区正常后续分区失效

问题核心错误 #

你的suffixArrayPartition函数存在致命逻辑错误：你直接将数组下标j和right作为后缀起始索引传入compareSuffix，但实际上suffixArray容器存储的才是各个后缀的起始位置，j和right只是数组自身的索引，并非后缀对应的字符串起始下标。这导致后续分区时比较的是错误的后缀，排序自然无法正常完成。

修复后的关键代码 #

修改后的suffixArrayPartition函数 #

int suffixArrayPartition(const std::string &text, std::vector<int> &suffixArray, int left, int right)
{
    int i = left - 1;
    // 提取基准元素对应的后缀起始索引
    int pivotSuffix = suffixArray[right];

    for (int j = left; j < right; j++)
    {
        // 比较当前数组元素对应的后缀与基准后缀
        if (compareSuffix(text, suffixArray[j], pivotSuffix) == -1)
        {
            i++;
            suffixArraySwap(suffixArray, j, i);
        }
    }

    suffixArraySwap(suffixArray, i + 1, right);

    return i + 1;
}

可选类型优化 #

suffixArrayQuickSort中p的类型无需使用unsigned int，改为int可避免不必要的类型转换，与函数参数类型保持一致：

void suffixArrayQuickSort(const std::string &text, std::vector<int> &suffixArray, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int p = suffixArrayPartition(text, suffixArray, left, right);

    suffixArrayQuickSort(text, suffixArray, left, p - 1);
    suffixArrayQuickSort(text, suffixArray, p + 1, right);
}

修复效果验证 #

修复后，后缀数组会按照后缀的字典序正确排序，例如前几项输出应为：

0:141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067
2:1592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067
15:238462643383279502884197169399375105820974944592307816406286208998628034825342117067
20:2643383279502884197169399375105820974944592307816406286208998628034825342117067
5:2653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067
...

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