gpt4 book ai didi

java - 调试 HeapSort Java 代码

转载 作者:行者123 更新时间:2023-11-29 05:36:35 25 4
gpt4 key购买 nike

我有一个随机生成的测试程序,数据是随机生成的,然后将它们传递给类 Sorter 的类构造函数。然后Sorter会对数据进行排序,通过一个方法传回给main函数。我还实现了其他几种排序方法作为 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;
}

}

最佳答案

我假设您有一个调试器,并且知道如何使用它。

在我看来,调试复杂代码的最佳方式就是我所说的“分而治之调试”。伪代码:

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() 没有发现有用的断点,因为第一个循环非常简单,而且不太可能出错,而第二个循环(调用 fixHeap)包含所有复杂性。

循环的第一次迭代没有发现任何改变,这是正确的,因为子树已经满足堆不变量。第二次迭代相同。

第三次迭代正确识别右 child 大于根,并交换两者。

第四次迭代发现没有任何变化,这是正确的。

所以它是包含问题的循环的最后一次迭代。两个 child 都比 parent 大。 fixHeap 正确地将较大的 child 移动到根中,并递归调用自身。该调用发现堆不变量得到满足,并返回。但返回后不满足不变量。

所以问题出在从检测堆不变性到返回的某个地方。检测检查:

        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 不应该吗?啊,这就是下一条语句的作用...

换句话说,我们在完成上一次更新之前检查堆不变量,然后完成该更新,这在这种情况下破坏了不变量......

关于java - 调试 HeapSort Java 代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19332634/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com