c++ - 使用 vector 的合并排序 C++

Question

我正在尝试使用合并排序方法使用 vector 而不是数组对文本文件进行排序。代码生成了，但是当我运行它时，我的一个 vector 出现了越界错误。

具体来说:

for (int k = start; k < end; k++)
{
    if (L.at(x) <= R.at(y))
    {
        v.at(k) = L.at(x);          // out of bounds
        x++;
    }
    else
    {
        v.at(k) = R.at(y);          // out of bounds
        y++;
    }

} 

我调整了 vector “v”的大小，但 int K 仍然增加到高。即 v 的大小将为 10，但 k 也将等于 10。我尝试更改一些值，但每次编译时函数最终都不会排序。我查找了各种合并排序方法，但每次我总是遇到相同的越界错误。

编辑: 我对我的循环进行了更改，现在它通过我的函数。但是他们返回一个空白 vector 。当我打印它时，整个“v” vector 都是空白。

完整代码:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std

vector<string> readFile(string fileName) {
    /* reads a textfile into vector. Works dandy. */ 
}

vector<string> merge(vector<string>& v, int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;

    vector<string> L;
    vector<string> R;

    L.resize(n1 + 1); // size left vector
    R.resize(n2 + 1); // size right vector

    for (int i = 1; i < n1; i++) {
        L.at(i) = v.at(start + i - 1); // populate left vector
    }
    for (int j = 1; j < n2; j++) {
        R.at(j) = v.at(mid + j);       // populate right vector
    }

    int x = 1;
    int y = 1;

for (int k = start; k < end; k++)
{
    if (L.at(x) <= R.at(y))
    {
        v.at(k) = L.at(x);          // merge left vector into v
            if (x < L.size() - 1)   // prevents x from increasing past bounds of L vector
            x++;
    }
    else
    {
        v.at(k) = R.at(y);          // merge right vector into v
        y++;
    }
    return v;
}

vector<string> mergeSort(vector<string>& v, int start, int end) {
    int middle;
    if (start < end)                    // base case
    {
        middle = (start + end) / 2;     // find middle
        mergeSort(v, start, middle);    // divide vectors
        mergeSort(v, middle + 1, end);
        merge(v, start, middle, end);   // merge sorted vectors
    }
    return v;
}

int main() {
    vector<string> vectorReadIn;
    vector<string> sortedVector;
    int x = 0;

    string fileName = "C:/Users/User/Downloads/Algorithims/Perm Words/perm15k.txt";

    vectorReadIn = readFile(fileName);    // reads file into vector

    sortedVector = mergeSort(vectorReadIn, 1, vectorReadIn.size());  // calls mergesort
    cout << "Sorted file:" << endl;
    while (x < 8) {
        cout << sortedVector.at(x);
        x++; 
    }
}

Answer 1

您对 vector 所做的所有索引都是从 1 开始的。 C++ vector (和数组)使用基于 0 的索引。至少，x 和 y 应该初始化为 0，i 和 j 种群中的索引循环应从 0 开始(适当更改结束条件和循环内的用法)，并且 main 中调用 mergeSort 的第二个参数应为 0，而不是1.