我的HeapSort代码有什么问题？

Question

我试图用java写一个heapsort方法，但它的工作方式并不完全像我想要的那样：

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。那么为什么它没有以正确的方式对数组进行排序呢？

Answer 1

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]

Answer 2

如果定义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]。