delete[] 语句卡住

Question

void shellSort1(T arr[], int n) {

	int h = 1;
	while (h < n / 3)
		h = 3 * h + 1;

	while (h >= 1) {

		for (int i = 0; i <= h - 1; i++) {
			for (int j = h + i; j < n; j += h) {

				T e = arr[j];
				int k = j;
				for (k = j; k > 0 && e < arr[k - h]; k -= h)
					arr[k] = arr[k - h];
				arr[k] = e;
			}

		}
		h /= 3;
	}
}

我自己按照定义写了一遍不优化的shellSort, 可以运行但是最后的delete[]语句会卡住，
Debug原因：A heap has been corrupted
什么原因怎么办呢？

Answer 1

liuyubobobo 2018-06-30 12:08:36

把你的逻辑替换到课程提供的补充代码的ShellSort中，看一下运行有没有问题？验证一下问题来自于ShellSort的内部还是外部？

课程补充代码提供的ShellSort传送门：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/02-Sorting-Basic/Course%20Code%20(C%2B%2B)/Optional-03-Shell-Sort/main.cpp

我怀疑问题来自于ShellSort外部，可能是某个数组空间被delete了两次：）

• 提问者 PTH #1

  找到问题了，只是数组越界了。神奇的是，错误的代码在N=20000刚好可以勉强运行只是不能delete，22000会卡死，40000才会abort....

• liuyubobobo 回复 提问者 PTH #2

  因为C++不做越界检查，所以有大名鼎鼎（臭名昭著）的undefined behavior啊！这也是C++容易写出有bug代码的根源：）