C++中vector<string>快速排序实现异常：字符串丢失且未排序问题求助

我帮你排查出了代码里的几个关键问题，这些正是导致字符串丢失、排序失效的根源：

1. Partition函数的循环起始索引错误 #

你的partition函数里，for循环的j从0开始，但实际上每次partition只需要处理[low, high]这个子区间。从0开始会错误地修改前面已经处理过的元素，导致区间外的元素被打乱，进而出现字符串丢失的情况。

修正： 把循环起始的j = 0改成j = low。

2. Partition函数的循环条件错误 #

当前循环条件是j <= high，但pivot本身是words[high]，我们不需要在循环里比较pivot——最后一步会专门把pivot放到正确的位置。如果包含high，会导致pivot被提前交换到前面，后续的交换操作会引发重复处理，破坏数组结构。

修正： 把循环条件改成j < high。

3. Get_sorted函数的索引越界问题 #

get_sorted里调用quicksort(words, 0, n_elems)，但vector的索引是从0开始的，最后一个元素的索引是n_elems - 1。传入n_elems会导致访问超出vector的范围，触发未定义行为（比如字符串丢失、程序崩溃）。

修正： 把n_elems改成n_elems - 1。

修正后的完整代码 #

int partition(std::vector<std::string>& words, int low, int high) {
    std::string pivot = words[high];
    int i = low - 1;
    // 修正：j从low开始，循环到high-1
    for (int j = low; j < high; j++) {
        if (words[j] < pivot) {
            i++;
            words[i].swap(words[j]);
        }
    }
    words[i+1].swap(words[high]);
    return i+1;
}

void quicksort(std::vector<std::string>& words, int low, int high) {
    if (low < high) {
        int part_idx = partition(words, low, high);
        quicksort(words, low, part_idx-1);
        quicksort(words, part_idx+1, high);
    }
}

void get_sorted(std::vector<std::string>& words, int n_elems) {
    // 修正：传入n_elems-1作为high参数
    quicksort(words, 0, n_elems - 1);
}

你可以测试一下这个版本，应该能正常完成原地排序，不会再出现字符串丢失的问题了。

内容的提问来源于stack exchange，提问作者Henrik Hillestad Løvold