2

我正在处理一个涉及 java 中的堆排序实现的作业问题。这是我到目前为止所拥有的

public class HeapSort {

    public static void maxHeapify(int[] a, int i) {
        int largest;
        int l = 2*i;
        int r = (2*i)+1;
        if (l<=a.length-1 && a[l]>a[i]) {
            largest = l;
        }
        else {
            largest = i;
        }
        if (r<a.length-1 && a[r]>a[largest]) {
            largest = r;
        }
        if (largest != i) {
            int temp = a[i];
            a[i] = a[largest];
            a[largest] = temp;
            maxHeapify(a,largest);
        }
    }

    public static void buildMaxHeap(int[] a) {
        for (int i=(a.length-1/2); i>=1; i--) {
            maxHeapify(a,i);
        }
    }

    public static void heapSort(int[] a) {
        buildMaxHeap(a);
        for (int i=a.length-1; i>=1; i--) {
            int temp = a[0];
            a[0] = a[i];
            a[0] = temp;
            maxHeapify(a,1);
        }
    }

这是我放在一起测试的主要内容（带输出）

public static void main(String[] args) {
    int[] tester = {3,2,9,45,7,15,21,11,36};
    System.out.println(Arrays.toString(tester));
    heapSort(tester);
    System.out.println(Arrays.toString(tester));
}

[3, 2, 9, 45, 7, 15, 21, 11, 36]
[3, 45, 36, 21, 9, 15, 2, 11, 7]

我目前没有收到任何错误，但输出有点偏离。很感谢任何形式的帮助。谢谢！

*编辑添加示例输出

4

2 回答 2

2

快速浏览一下，我会说您错过了一些对 maxHeapify() 的调用。看起来你只有 maxHeapify() 堆的一半（在最右边的分支结束的一半），而不是其余的。您必须为 a[0] 到 a[length/2] 中的所有元素调用 maxHeapify()。

您应该将对 maxHeapify() 的递归调用移出交换条件。对于堆的初始构建，您必须一直传播到根。而且你不是 maxHeapify() '最大'元素，而是堆上一层的元素，所以总是如此i/2。

于 2013-02-22T07:24:37.993 回答
0 
    if (r<a.length-1 && a[r]>a[largest]) {
        largest = r;
    }

应该

    if (r<=a.length-1 && a[r]>a[largest]) {
        largest = r;
    }

我相信您还必须调用maxHeapify(a,0);而不是maxHeapify(a,1);在最后一个循环中调用。除了上面提到的评论中的 -1/2 排序问题。那应该做的工作。

于 2013-02-22T07:31:58.243 回答