我的HeapSort代码有什么问题？

Question

我的HeapSort代码有什么问题？

6

我正在尝试用Java编写堆排序方法，但它并不完全按照我的意愿工作：

public class HeapSort {

    private static int n;

    private static void swap(int[] A, int a, int b)
    {
        int tmp = A[a];
        A[a] = A[b];
        A[b] = tmp;
    }

    private static void insert(int[] A, int i)
    {
        int left = i * 2;
        int right = left + 1;
        int max = i;

        if (left <= n && A[left] < A[max]){ 
            max = left;
        }
        if (right <= n && A[right] > A[max]) {
            max = right;
        }
        if (max != i) {
            swap(A, i, max);
            insert(A, max);
        }
    }

    public static void HeapSort(int[] A)
    {
        n = A.length - 1;

        for (int i = n / 2; i >= 0; i--)
            insert(A, i);

        for (int i = n; i > 0; i--) {
            swap(A, 0, i);
            n--;
            insert(A, 0);
        }
    }

    public static void main(String[] args){
        int[] A = new int[] {9, 2, 8, 1, 4};
        System.out.println(java.util.Arrays.toString(arr));
        HeapSort(A);
        System.out.println(java.util.Arrays.toString(arr));
    }
}

它可以处理某些数组，但像9、2、8、1、4这样的数组将被排序为1、4、2、8、9。那么为什么它不能按正确的方式对数组进行排序呢？

- david mah

2个回答

0

如果你定义 left = i * 2，那么你堆的根应该存储在 A[1] 而不是 A[0]。通过不使用数组索引 0，你可以始终说一个节点 i 的左右孩子分别是 2*i 和 2*i+1。

基本上，在你的 HeapSort 中，你应该将 0 改为 1（共有 4 处）。用数组 {0, 9, 2, 8, 1, 4} 进行测试。

另外，在 insert 中比较也是错误的。它应该是 A[left] > A[max]。

- dejvuth

它适用于9、2、8、1、4，但对于0、9、2、8、1、4，它将其返回为1、2、4、8、9、0。为什么会这样做？ - david mah

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user109260 · Accepted Answer

if (left <= n && A[left] > A[i]){ 
     max = left;
}

试试这个并看看效果。我已经完成了下面的完整程序。这对你提供的输入有效。

public class HeapSort {

private static int n;

private static void swap(int[] A, int a, int b)
{
    int tmp = A[a];
    A[a] = A[b];
    A[b] = tmp;
}

private static void insert(int[] A, int i)
{
    int left = i * 2;
    int right = left + 1;
    int max = i;

    if (left <= n && A[left] > A[i]){ 
        max = left;
    }
    if (right <= n && A[right] > A[max]) {
        max = right;
    }
    if (max != i) {
        swap(A, i, max);
        insert(A, max);
    }
}

public static void HeapSort(int[] A)
{
    n = A.length - 1;

    for (int i = n / 2; i >= 0; i--)
        insert(A, i);

    for (int i = n; i > 0; i--) {
        swap(A, 0, i);
        n--;
        insert(A, 0);
    }
}

public static void main(String[] args){
    int[] A = new int[] {19, 6, 28, 1, 0};
    int[] B = new int[] {1, 2, 4, 8, 9, 0};
    System.out.println(java.util.Arrays.toString(A));
    System.out.println(java.util.Arrays.toString(B));
    HeapSort(A);
    HeapSort(B);
    System.out.println(java.util.Arrays.toString(A));
    System.out.println(java.util.Arrays.toString(B));
}

}

这是输出结果。

[19, 6, 28, 1, 0]
[1, 2, 4, 8, 9, 0]
[0, 1, 6, 19, 28]
[0, 1, 2, 4, 8, 9]