C++ 中的数组和合并排序？

Question

void Merge(int *array, int lo, int mid, int hi) {
    int tArray[20];
    int loBeg = lo;
    int count = lo;
    int hiBeg = mid + 1;
    while (loBeg <= mid && hiBeg <= hi) {
        if (array[loBeg] < array[hiBeg]) {
            tArray[count] = array[loBeg];
            loBeg++;
            count++;
        } else {
            tArray[count] = array[hiBeg];
            hiBeg++;
            count++;
        }
    }
    while (loBeg <= mid) {
        tArray[count++] = array[loBeg++];
    }
    while (hiBeg <= hi) {
        tArray[count++] = array[hiBeg++];
    }
    for (int i = 0; i < count; i++) {
        array[i] = tArray[i];
    }
}

void mergeSort(int *array, int lo, int hi) {
    if (lo < hi) {
        int mid = (lo + hi) / 2;
        mergeSort(array, lo, mid);
        mergeSort(array, mid + 1, hi);
        Merge(array, lo, mid, hi);
    }
}

int main(int argc, const char * argv[]) {
    int array[] = {90, 99, 63, 82, 93, 76, 81, 76};
    //int temp[8];
    mergeSort(array, 0, 7);
    for (int i = 0; i < 8; i++) {
        std::cout << array[i] << std::endl;
    }
    return 0;
}

我的问题是关于此合并排序代码中数组的性质。此代码仅在 Merge 中有效，O 将 tArray[20]; 设置为初始值为 20。为什么我不能将初始值设置为 hi + 1，在本例中为 8（相同作为数组）？但是，如果我取消注释掉 temp[8] 数组，并将其传递给 mergeSort 和 Merge，并将其用作 Merge 中的 tArray（初始8) 的大小，然后它就可以工作了。

我想我的理解不足也是我原来的merge()（见下文）功能不起作用的原因：

    //this was my original merge code which does not work.
    void merge(int *array, int lo, int mid, int hi) {
        int tempArray[hi + 1];
        int loBeg = lo;
        int hiBeg = mid + 1;
        for (int i = 0; i <= hi; i++) {
            if (hiBeg > hi || (array[loBeg] < array[hiBeg] && loBeg <= mid)) {
                tempArray[i] = array[loBeg++];
            } else {
                tempArray[i] = array[hiBeg++];
            }
        }
        for (int i = 0; i <= hi; i++) {
            array[i] = tempArray[i];
        }
    }

所以基本上我想知道为什么在第一个 Merge() 函数中，我必须将 tArray 初始大小设置为 20 而不是与数组相同的大小，除非我从 main 传递一个临时数组（它被初始化为与数组大小相同）然后此外，为什么我原来的 merge() 函数不起作用，但我认为这与我的缺乏有关了解第一个 Merge() 函数。

Answer 1

合并排序被认为适用于列表，因为当您合并 2 个列表时，您可以自由地将每个元素附加到您想要的元素。

示例：

Merge(List{3,4},List{5,6});

结果如下

List Merge(List a, List b){ //2 instructions even when Lists are long 1000000 elements
    List newlist;
    newlist.head = a.head;
    newlist.tail = b.tail;
    a.tail.next = b.head;
    b.head.prev = a.tail;
    return newList;
}

当你有数组时，你实际上必须分配一个新大小的新数组：

int * Merge( int array* a, int array* b, unsigned int sizea, unsigned int sizeb){
    //int tArray[20]; // :/ wrong
    int * newarray = new int[sizea+sizeb];

    for(unsigned int i=0; i<sizea; i++)
        newarray[i]=a[i];

    for(unsigned int i=0; i<sizeb; i++)
        newarray[i+sizea]=a[i];

    delete []a;
    delete []b;
    return newarray;
}

顺便说一下，这会使算法变得更加昂贵。即使在您预先分配了足够大的数组的情况下，算法的成本也会更高，因为您必须在每次合并时复制所有元素。

Answer 2

当您创建这样的数组时 int array[20]; 您是在程序的堆栈内存中分配它。该内存在程序启动之前分配。

你的问题来了。当您尝试执行 int array[hi + 1]; 时，您要求它分配程序启动前未知的内存量，这会导致错误。

在这种情况下，您需要做的是使用动态内存。此内存在运行上分配和释放。这意味着您可以执行 int* array = new int[hi + 1]; 并且不会导致错误。

整个合并函数为：

void merge(int *array, int lo, int mid, int hi) {
    int* tempArray = new int[hi + 1];
    int loBeg = lo;
    int hiBeg = mid + 1;
    for (int i = 0; i <= hi; i++) {
        if (hiBeg > hi || (array[loBeg] < array[hiBeg] && loBeg <= mid)) {
            tempArray[i] = array[loBeg++];
        } else {
            tempArray[i] = array[hiBeg++];
        }
    }
    for (int i = 0; i <= hi; i++) {
        array[i] = tempArray[i];
    }

    delete[] tempArray;
}

我不建议您自己管理动态内存。您应该为此使用 STL：vector<int> tempArray(hi + 1); 而不是 int* tempArray = new int[hi + 1];。这样你就不必在最后有 delete[] tempArray;。

Answer 3

您的代码中存在多个问题，以下是其中的几个：

void Merge(int *array, int lo, int mid, int hi) {
    // The size should be hi - lo + 1, not hi + 1
    int tArray[hi + 1];
    int loBeg = lo;
    // count should start at 0, not lo
    int count = lo;
    int hiBeg = mid + 1;
    while (loBeg <= mid && hiBeg <= hi) {
        if (array[loBeg] < array[hiBeg]) {
            tArray[count] = array[loBeg];
            loBeg++;
            count++;
        } else {
            tArray[count] = array[hiBeg];
            hiBeg++;
            count++;
        }
    }
    while (loBeg <= mid) {
        tArray[count++] = array[loBeg++];
    }
    while (hiBeg <= hi) {
        tArray[count++] = array[hiBeg++];
    }
    for (int i = 0; i < count; i++) {
        // it should be array[lo + i], not array[i]
        array[i] = tArray[i];
    }
}

以下是对这 3 个错误的一些解释：

你不想每次都使用hi + 1大小的数组，当你向下"merging tree"时，你必须合并较小大小的数组，所以你需要使用 hi - lo + 1。实际上，在这种情况下使用 hi + 1 应该不是问题，但是您分配的内存比实际需要的多。
您不应从 lo 开始，而应从 0 开始，否则您的 tArray[count] 将出界。从 lo 开始适用于您的情况，因为您正在分配一个非常大的数组（大小为 20 或 hi + 1），但它不适用于大小为 [=13= 的数组],所以你要小心了。
也许是最大的错误 - 您总是替换原始数组的第一个 count 单元格...不！您想要替换 lo 和 hi 之间的单元格，而不是 0 和 count 之间的单元格。

你需要记住，当你调用Merge (array, lo, mid, hi)时，你想要将array[lo:mid]和array[mid+1:hi]合并为array[lo:hi]。

这里有一些详细的解释：

让我们从以下数组 [90, 99, 63, 82, 93, 76, 81, 76] 开始，在每次调用 mergeSort 时，您将数组分成 2 个相等的部分：

第一次获得[90, 99, 63, 82]（lo = 0、hi = 3）和[93, 76, 81, 76]（lo = 4和hi = 7），并且你继续划分，直到你有 8 个大小为 1 的数组。我会写 (array, lo, hi)，例如([90], 0, 0) 为简单起见。

你应该达到 ([90], 0, 0)、([99], 1, 1) 等的地步......你将把这些 2 乘 2 合并，所以你（例如）要合并([93], 4, 4) 和 ([76], 5, 5)。当你合并这两个数组时，你会得到一个 Merge 的调用，如下所示：

Merge (array, 4, 4, 5) // mid is (4 + 5) / 2 = 4

那么，Merge 函数中发生了什么？

您应该已经注意到，由于您正在合并两个大小为 1 的数组（[93] 和 [76]），因此您需要一个大小为 2 的临时数组。如果您使用tArray[hi + 1]，你分配了一个大小为 hi + 1 = 6 的数组，这比你实际需要的大很多（这里可能没有太大区别，但想象一下如果你有一个大小为十亿的原始数组！ ).所以分配一个大小为 hi - lo + 1 = 5 - 4 + 1 = 2 的数组就足够了。
你实际上是初始数组的范围4到5，所以你想处理那部分，你不想擦除那部分0 到 1 您已经排序了！但是如果你在循环中执行 array[i] = tArray[i] 会发生什么？好吧，i 从 0 开始到 count（在这种情况下应该是 2），所以你要替换 array[0] 和 array[1] 而不是 array[4] 和 array[5]。这可以通过 array[lo + i] 而不是 array[i].

C++ 中的数组和合并排序？

Arrays and mergeSort in c++?

c++

arrays

mergesort