0

我正在编写一个应该使用归并排序对数组进行排序的函数。到目前为止，我有两个功能：

template <typename Item, typename SizeType>
void merge_sort(Item data[], SizeType size) {
SizeType size1, size2;
if(size > 1) {
    size1 = size/2;
    size2 = size - size1;
    merge_sort(data,size1);
    merge_sort((data+size1),size2);

    merge(data,size1,size2);
}
}

和：

template <typename Item, typename SizeType>
void merge(Item data[], SizeType size1, SizeType size2) {
Item* temp;
SizeType copied = 0;
SizeType copied1 = 0;
SizeType copied2 = 0;

temp = new Item[size1 + size2];

while(copied1 < size1 && copied2 < size2) {
    if(data[copied1] < (data + size1)[copied2])
        temp[++copied] = data[++copied1];
    else
        temp[++copied] = (data + size1)[++copied2];
}

while (copied1 < size1)
    temp[++copied] = data[++copied1];
while (copied2 < size2)
    temp[++copied] = (data + size1)[++copied2];

for(SizeType i = 0; i < size1 + size2; ++i)
    data[i] = temp[i];
delete [] temp;
}

然而，当我尝试运行该程序时，我收到一个调试错误，指出堆在正常块后损坏，并且 CRT 检测到应用程序在堆缓冲区结束后写入内存。谁能解释这意味着什么以及我该如何解决？

4

3 回答 3

2

在使用这些值之前您正在递增......所以基本上使检查过时......

改为使用copied++。

您需要后增量运算符，因为如果在使用它之前对其进行增量，则会超出范围。 递增和递减运算符

于 2012-12-06T19:34:43.897 回答
2

你的意思是你的增量是后增量而不是前增量？例如：

    temp[copied++] = (data + size1)[copied2++];

使用预增量，在第一次迭代时copied2，0您正在访问(data + size1)[1]. 当copied2到达分配内存的末尾时，您正在访问末尾的内存。

为避免这种情况，我建议不要将增量作为子表达式。写作和阅读可能会令人困惑。

于 2012-12-06T19:37:09.803 回答
1

如果已复制 = 0 且已复制 1 = 0 则行

临时[++复制] = 数据[++复制1]；

会产生

温度[1] = 数据[1]；

因为前缀 ++ 在这里具有最高优先级

于 2012-12-06T19:42:23.867 回答