调试HeapSort Java代码
我有一个测试程序随机生成数据，然后把它们传递给类构造器类Sorter。然后Sorter将对数据进行排序，并将其通过一个方法传递回主函数。我还实现了其他几种排序方法，作为Sorter类的子类，它们工作得很好。所以我觉得我的“索特”课没有问题。下面是我的测试程序在使用堆排序时的输出。
数据：
48 96 71 81 78 72 93 52 67 70
分类数据：
48 71 81 78 72 67 52 93 70 96
如您所见，数据在通过以下代码后没有排序。下面是密码。
public class HeapSort extends Sorter{
private int[] heap;
private int size;
public HeapSort(int[] data){
super(data);
}
public void sort(){
constructHeap();
for(int i = size - 1; i >= 0; i--){
numbers[i] = extractMax();
}
}
public void constructHeap(){
size = numbers.length;
heap = new int[size];
for(int j = 0; j < size; j++) heap[j] = numbers[j];
for(int i = size/2 - 1; i >= 0; i--){
fixHeap(i, heap[i]);
}
}
public int extractMax(){
int max = heap[0];
fixHeap(0, heap[--size]);
return max;
}
public void fixHeap(int pos, int key){
if(left(pos) > size) heap[pos] = key; // if current position is leaf
else{
int largest = pos;
int r = right(pos);
int l = left(pos);
if(r < size && heap[largest] < heap[r]) largest = r;
if(l < size && heap[largest] < heap[l]) largest = l;
if(largest == pos) heap[pos] = key;
else{
heap[pos] = heap[largest];
fixHeap(largest, key);
}
}
}
public int left(int i){return 2*i+1;}
public int right(int i){return 2*i+2;}
}编辑:下面是调试的代码。希望有人会发现它有用。
public class HeapSort extends Sorter{
private int[] heap;
private int size;
public HeapSort(int[] data){
super(data);
}
public void sort(){
constructHeap();
for(int i = size - 1; i >= 0; i--){
numbers[i] = extractMax();
}
}
public void constructHeap(){
size = numbers.length;
heap = new int[size];
for(int j = 0; j < size; j++) heap[j] = numbers[j];
for(int i = size/2 - 1; i >= 0; i--){
fixHeap(i);
}
}
public int extractMax(){
int max = heap[0];
heap[0] = heap[--size];
fixHeap(0);
return max;
}
public void fixHeap(int pos){
if(left(pos) < size){ // if current position is not leaf
int largest = pos;
int r = right(pos);
int l = left(pos);
if(r < size && heap[largest] < heap[r]) largest = r;
if(l < size && heap[largest] < heap[l]) largest = l;
if(largest != pos){
exchange(pos, largest);
fixHeap(largest);
}
}
}
public int left(int i){return 2*i+1;}
public int right(int i){return 2*i+2;}
public void exchange(int a, int b){
int temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
}回答 1
Stack Overflow用户
发布于 2013-10-12 10:18:32
我假设您有一个调试器，并且知道如何使用它。
在我看来，调试复杂代码的最佳方法是我所说的“分而治之调试”。伪码：
void debug(Time beforeTheBug, Time afterTheBug) {
do {
Time pivot = between(beforeTheBug, afterTheBug);
if (stateIsAsExceptedAt(pivot)) {
afterTheBug = pivot;
} else {
beforetheBug = pivot;
}
} while (amountOfCodeExecutedBetween(beforeTheBug, afterTheBug) is not trivial);
}在您的例子中，我的第一个检查是输出。实际上，它没有被排序，所以这个bug在这个类中。
我的下一个检查是在constructHeap之后堆不变量是否满足。那时，heap是96，48，93，81，78，72，71，52，67，70，所以堆不变量不满足(48不大于78)，并且在堆的构造过程中会发生错误。
查看constructHeap()没有发现有用的断点，因为第一个循环非常simpe，不太可能出错，而第二个循环(及其对fixHeap的调用)包含了所有的复杂性。
循环的第一次迭代没有发现任何改变，这是正确的，因为子树已经满足堆不变。第二次迭代也是如此。
第三次迭代正确地识别了正确的子级大于根，并交换了这两个项。
第四次迭代没有发现任何改变，这是正确的。
因此，包含问题的是循环的最后一次迭代。两个孩子都比父母大。fixHeap正确地将更大的子节点移动到根中，并递归地调用自身。该调用发现堆不变满足，并返回。但不变量在返回后不满足。
所以问题就在从检测堆不变量到返回的某个地方。侦查检查：
if (r < size && heap[largest] < heap[r])
largest = r;
if (l < size && heap[largest] < heap[l])
largest = l;其中heap为96、96、93、81、78、72、71、52、67、70。是的，96大于81和78。但实际上，heap[pos] == key不应该吗？啊，下一份声明就是这样.
换句话说，我们在完成上一次更新之前检查堆不变量，然后完成更新，这在本例中破坏了不变量.
https://stackoverflow.com/questions/19332634
复制相似问题
腾讯云开发者
