C++快速排序实现出现Segmentation Fault问题求助

核心原因 #

你判断的完全正确——std::size_t是无符号整数类型，无法表示负数。当用它作为排序的索引/指针变量时，一旦执行类似rhs_pointer--的操作，若变量当前值为0，减1会触发无符号溢出，直接变成该类型的最大值（比如64位系统上的18446744073709551615），此时访问container[lhs_pointer]必然会越界，触发Segmentation Fault。

修复步骤 #

1. 替换索引类型 #

把排序函数中所有用于定位的std::size_t替换为有符号整数类型，推荐用std::ptrdiff_t（专门用于表示指针差值的标准有符号类型，适配所有容器的迭代器差值），或者直接用int（针对小范围容器足够安全）。

2. 修正循环边界逻辑 #

以升序排序的分区循环为例，原代码的条件需要调整，避免无符号溢出和死循环：

// 原错误代码（size_t版本）
while(container[lhs_pointer] <= pivot_element && lhs_pointer < rhs_pointer) {
    lhs_pointer++;
}
while(container[rhs_pointer] >= pivot_element && lhs_pointer < rhs_pointer) {
    rhs_pointer--; // rhs_pointer为0时，size_t溢出成极大值
}

替换为有符号类型后的修正代码：

// 修正后（std::ptrdiff_t版本）
using Index = std::ptrdiff_t;
Index lhs = start;
Index rhs = end;
const auto pivot = container[(start + end) / 2];

// 调整循环条件，避免溢出和死循环
while (lhs <= rhs) {
    while (container[lhs] < pivot) {
        lhs++;
    }
    while (container[rhs] > pivot) {
        rhs--;
    }
    if (lhs <= rhs) {
        std::swap(container[lhs], container[rhs]);
        lhs++;
        rhs--;
    }
}

3. 递归调用边界校验 #

确保递归时传入的索引始终在合法范围内，比如：

if (start < rhs) {
    quick_forward_order(container, start, rhs);
}
if (lhs < end) {
    quick_forward_order(container, lhs, end);
}

4. 边界场景测试 #

测试时重点覆盖：空容器、单元素容器、全重复元素容器、完全逆序容器，验证修复后不会出现越界问题。

额外优化建议 #

• 优先使用容器的iterator而非索引编写模板函数，迭代器的差值天然是std::ptrdiff_t，能从根源避免无符号溢出问题，同时适配所有STL容器（比如list这类不支持随机访问的容器）。
• 调试时可以用gdb的print命令查看段错误发生时的索引值，直接确认是否是无符号溢出导致的越界。

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