c++ - 使用 Vectors 的 Mergesort 排序不正确

Question

我正在研究 Mergesort 以刷新我对它的内存。我是根据我创建的人的文本文件来做的。出于某种原因，我似乎无法调试......排序根本没有真正排序任何东西。我有正确的函数和循环，但肯定有一些我没有注意到的小事。我将不胜感激任何帮助。谢谢!

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

using namespace std;

struct Person {
    string DOB;
    string balance;
    string firstName;
    string lastName;
    string state;

    Person() { }

    Person(string DOB, string firstName, string lastName, string state, string balance) {
        this->DOB = DOB;
        this->firstName = firstName;
        this->lastName = lastName;
        this->state = state;
        this->balance = balance;
    }

    void print() {
        cout << DOB << " "
        << balance << " "
        << firstName<< " "
        << lastName << " "
        << state  << " "
        << balance  << "\n";
    }
};

void print(vector<Person*> arr, int size) { // print function for array debuggin'
    for (int i = 0; i < size - 1; i++) {
        cout << arr[i]->lastName << " | ";
    }
    cout << endl;
}

void merge(vector<Person*> arr, int start, int mid, int end) {
    int leftSize = mid - start + 1;
    int rightSize = end - mid;
    int leftIndex, rightIndex;
    int masterIndex = start;

    vector<Person*> tmpR; // arrays to represent our two sections of the total array
    vector<Person*> tmpL;

    for (leftIndex = 0; leftIndex < leftSize; leftIndex++) { // copying our values from our master array into our subarrays
        tmpL.push_back(arr[leftIndex]);
    }
    for(rightIndex = 0; rightIndex < rightSize; rightIndex++) {
        tmpR.push_back(arr[rightIndex]);
    }

    //print(tmpL, leftSize); // print those sub arrays out for debugging
    //print(tmpR, rightSize);

    leftIndex = 0;
    rightIndex = 0;

    while (leftIndex < leftSize && rightIndex < rightSize) { // compares L and R subarrays and picks the last name first in the alphabet to go first
        if (tmpL[leftIndex]->lastName < tmpR[rightIndex]->lastName) {
            arr[masterIndex] = tmpL[leftIndex];
            leftIndex++;
        } else {
            arr[masterIndex] = tmpR[rightIndex];
            rightIndex++;
        }
        masterIndex += 1;
    }

    while (leftIndex < leftSize) { // the two following while conditions empty the remaining ordered last names from the subArray that is not empty
        arr[masterIndex] = tmpL[leftIndex];
        leftIndex++;
        masterIndex++;
    }
    while (rightIndex < rightSize) {
        arr[masterIndex] = tmpR[rightIndex];
        rightIndex++;
        masterIndex++;
    }

}

void split(vector<Person*> arr, int start, int end) {
    if (start < end) {
        int mid = (start+end) / 2;
        split(arr, start, mid);
        split(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

void readIn() {
    string DOB;
    string ssNumber;
    string bankBalance;
    string firstName;
    string lastName;
    string state;
    int size;
    vector<Person*> pVector;

    ifstream fin;
    fin.open("data1.txt");
    if (fin.fail()) {
        cout << ("error reading file");
        exit(1);
    }

    while (!fin.eof()) { // pulls in our data and stores it in a poiinter to a person object
        fin >> DOB >> ssNumber >> firstName >> lastName >> state >> bankBalance;
        Person *tmp = new Person(DOB, firstName, lastName, state, bankBalance);
        pVector.push_back(tmp);
    }
    size = (int) pVector.size() - 1;

    fin.close(); // closes the input stream previously opened.
    cout << size << endl;
    sleep(2);

    split(pVector, 0, size-1);

    for (int i = 0; i < size; i++) {
        cout << pVector[i]->lastName << endl;
    }
}

int main() {
    readIn();
    return 0;
}

Answer 1

据我所知，您正在按值传递 vector，即它被复制并且在调用站点上您保留原始的。

尝试通过引用传递 vector 。

void split(vector<Person*>&    arr, int start, int end) {
                         ^^^

void merge(vector<Person*>& arr, int start, int mid, int end) {
                         ^^^

void print(vector<Person*> const& arr, int size) {
                          ^^^^^^^  // You don't want to modify it here