c++ - 合并排序算法无法正常工作

Question

作为家庭作业的一部分，我需要能够使用结构作为主要参数来实现合并排序。直到今天才熟悉合并排序，我试图编写自己的实现。出于某种原因，我无法让它工作。

这是我的代码:

#include<iostream>
#include<stdlib.h>

using namespace std;

struct MergeArgument
{
    int *numArray;
    int *tempArray;
    int lowIndex, highIndex;
};

void merge(MergeArgument*);
void merge_sort(MergeArgument*);

int main(int argc, char** argv)
{   int SIZE = 25;
    MergeArgument arg;
    int arr[SIZE];
    int temp[SIZE];

    for(int k = 0; k < SIZE; k++)
    {
        arr[k] = rand() % 100;
        cout << arr[k] << " ";
    }

    arg.numArray = arr;
    arg.tempArray = temp;
    arg.lowIndex = 0;
    arg.highIndex = SIZE - 1;

    cout << endl;

    merge_sort(&arg);

    cout << "Sorted array: \n";

    for (int i = 0; i < SIZE; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}

void merge_sort(MergeArgument *arg)
{   int tempHigh, tempLow;
    if(arg->lowIndex < arg->highIndex)
    {
        tempHigh = arg->highIndex;
        tempLow = arg->lowIndex;
        arg->highIndex = (tempHigh + tempLow) / 2;
        merge_sort(arg);
        arg->highIndex = tempHigh;
        arg->lowIndex = ((tempHigh + tempLow) / 2) + 1;
        merge_sort(arg);
        arg->lowIndex = tempLow;
        merge(arg);
    }

}

void merge(MergeArgument *arg)
{   int low = arg->lowIndex, mid = ((arg->lowIndex + arg->highIndex) / 2), high = arg->highIndex;
    int i = low, lowCounter = low, highCounter = mid + 1;

    while((lowCounter <= mid) && (highCounter <= high))
    {
        if(arg->numArray[lowCounter] < arg->numArray[highCounter])
        {
            arg->tempArray[i] = arg->numArray[lowCounter];
            lowCounter++;
        }
        else
        {
            arg->tempArray[i] = arg->numArray[highCounter];
            highCounter++;
        }
        i++;
    }

    if (lowCounter < mid)
    {
        for (int k = lowCounter; k < mid; k++)
        {
            arg->tempArray[i] = arg->numArray[k];
            i++;
        }
    }
    else
    {
        for (int k = highCounter; k <= arg->highIndex; k++)
        {
            arg->tempArray[i] = arg->numArray[k];
            i++;
        }

    }

    for(int k = arg->lowIndex; k <= arg->highIndex; k++)
    {
        arg->numArray[k] = arg->tempArray[k];
    }
}

这是我得到的输出:

83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82    
Sorted array:  
11 -1216235240 15 0 21 26 -1079135248 26 27 -1079135396 29 -1216770650 35 -1216235240 49 -1216492084 59 0 68 72 82 83 0 86 82

谁能指出我到底做错了什么？

Answer 1

这已经非常接近工作了，尽管您可能想要考虑人们就使它更像 C++ 所做的一些评论。毫无疑问，这是来之不易的经验，没有足够的时间回去做你真正应该做的事。

我看到的问题在这里，在 merge 中:

if (lowCounter < mid)
{
    for (int k = lowCounter; k < mid; k++)
    {
        arg->tempArray[i] = arg->numArray[k];
        i++;
    }
}

您可能想要将此处的边界与初始循环进行比较和对比。