C++归并排序出现Vector subscript out of range错误的解决及原因咨询

嘿，我来帮你搞定这个归并排序的问题！

1. vector subscript out of range #

这个错误直白点说就是：你试图访问vector里根本不存在的位置啦！vector的下标是从0开始的，比如一个size为5的vector，有效下标是0、1、2、3、4，如果你去访问下标5，就会触发这个错误——因为这个位置没有元素。

2. 断言失败（Assertion Failed） #

断言（assert）是代码里用来检查“必须满足的条件”的工具，比如你可能写了assert(index < numbers.size())来确保下标合法。当你传的参数让这个条件不成立时，程序就会触发断言失败，直接终止运行，告诉你哪里出问题了。

你调用mergeSort(numbers,0,numbers.size())的时候，把右边界传成了numbers.size()，但这个值对应的下标是不存在的（vector最后一个元素的下标是size()-1）。如果你的归并排序实现是按**闭区间[left, right]**来处理的（也就是包含left和right对应的元素），那访问numbers[right]的时候就会直接越界，同时触发断言失败。

根据你的归并排序实现逻辑，选一种适配的方式：

思路1：改成闭区间调用（最常见的实现方式） #

把调用改成：

mergeSort(numbers, 0, numbers.size() - 1);

同时确保你的mergeSort和merge函数是按闭区间处理的，比如参考这个实现：

#include <vector>
#include <iostream>
using namespace std;

void merge(vector<int>& nums, int left, int mid, int right) {
    // 临时数组存合并后的结果
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    
    // 合并两个有序子数组
    while (i <= mid && j <= right) {
        temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
    }
    // 把剩下的元素拷贝进去
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= right) temp[k++] = nums[j++];
    
    // 把临时数组的内容拷回原数组
    for (int p = 0; p < temp.size(); p++) {
        nums[left + p] = temp[p];
    }
}

void mergeSort(vector<int>& nums, int left, int right) {
    // 区间只有0或1个元素，无需排序
    if (left >= right) return;
    
    int mid = left + (right - left) / 2; // 避免溢出
    mergeSort(nums, left, mid);          // 排序左半部分[left, mid]
    mergeSort(nums, mid + 1, right);     // 排序右半部分[mid+1, right]
    merge(nums, left, mid, right);       // 合并两个有序子数组
}

int main() {
    vector<int> numbers = {3,1,4,1,5,9,2,6};
    mergeSort(numbers, 0, numbers.size() - 1);
    
    for (int num : numbers) {
        cout << num << " ";
    }
    return 0;
}

思路2：适配左闭右开区间 #

如果你想保留mergeSort(numbers,0,numbers.size())的调用方式，那就要把实现改成左闭右开区间[left, right)（包含left，不包含right）。这种方式下，right可以是numbers.size()，因为我们不会访问这个下标：

#include <vector>
#include <iostream>
using namespace std;

void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left);
    int i = left, j = mid, k = 0;
    
    while (i < mid && j < right) {
        temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
    }
    while (i < mid) temp[k++] = nums[i++];
    while (j < right) temp[k++] = nums[j++];
    
    for (int p = 0; p < temp.size(); p++) {
        nums[left + p] = temp[p];
    }
}

void mergeSort(vector<int>& nums, int left, int right) {
    // 区间长度<=1，无需排序
    if (right - left <= 1) return;
    
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid);    // 排序[left, mid)
    mergeSort(nums, mid, right);   // 排序[mid, right)
    merge(nums, left, mid, right); // 合并两个区间
}

int main() {
    vector<int> numbers = {3,1,4,1,5,9,2,6};
    mergeSort(numbers, 0, numbers.size());
    
    for (int num : numbers) {
        cout << num << " ";
    }
    return 0;
}

• 核心问题是调用的区间定义和实现逻辑不匹配，导致访问了不存在的vector下标。
• 选一种区间方式（闭区间/左闭右开），保持调用和实现一致就解决啦！

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