java - 我的 HeapSort 代码有什么问题？

Question

我正在尝试用 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。那么为什么它不能以正确的方式对数组进行排序？

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]