我正在编写一个应该使用合并排序对数组进行排序的函数。到目前为止,我有两个功能:
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 检测到应用程序在堆缓冲区结束后写入内存。谁能解释一下这意味着什么以及我如何解决它?
您在使用值之前递增...所以这基本上使检查过时了...
请改用copied++
。
您需要后递增运算符,因为如果在使用它之前递增它,则会超出界限。递增和递减运算符
您的意思是增量后而不是前增量吗?例如:
temp[copied++] = (data + size1)[copied2++];
使用预增量,在第一次迭代中,当copied2
0
时,您正在访问(data + size1)[1]
。当copied2
到达分配的内存末尾时,您正在访问一个超过末尾的内存。
为了避免这种情况,我建议不要将增量作为子表达式。写作和阅读可能会令人困惑。
如果复制 = 0 并且复制 1 = 0,则
行temp[++copied] = data[++copied1];
将产生
温度[1] = 数据[1];
因为前缀++在这里具有最高优先级