这有什么错我的堆排序code？ [英] What's wrong with my HeapSort code?

问题描述

我试图用Java编写一个堆排序方法，但它不完全工作，我希望它：

 公共类堆排序{    私有静态诠释N;    私有静态无效掉期（INT [] A，int类型的，INT B）
    {
        INT TMP = A [A];
        A [A] = A [B]。
        A [B] = tmp目录;
    }    私有静态无效插入（INT [] A，int i）以
    {
        INT左= I * 2;
        INT右=左+ 1;
        INT最大= I;        如果（左＆LT; = N＆放大器;＆安培; A [左]＆LT; A [MAX]）{
            最大=左;
        }
        如果（右LT; = N＆放大器;＆安培; A [右]＆gt;将[MAX]）{
            MAX =权利;
        }
        如果（最大值！=ⅰ）{
            掉期（A，I，最大值）;
            插入（A，最大值）;
        }
    }    公共静态无效堆排序（INT [] A）
    {
        N =则为a.length  -  1;        的for（int i = N / 2; I＆GT; = 0;我 - ）
            插入（A，I）;        的for（int i = N; I＆GT; 0;我 - ）{
            掉期（A，0，I）;
            N--;
            插入（A，0）;
        }
    }    公共静态无效的主要（字串[] args）{
        INT [] A = INT新[] {9,2，8,1，4};
        的System.out.println（java.util.Arrays.toString（ARR））;
        堆排序（A）;
        的System.out.println（java.util.Arrays.toString（ARR））;
    }
}
 

它的工作原理与某些阵列阵列但像9,2，8,1，4会得到正确的方式分成1，4，2，8，9，那么，为什么是不是排序的数组？

解决方案

 如果（左＆LT; = N＆放大器;＆安培; A [左]＆gt;在[I]）{
     最大=左;
}
 

试试这个，看看。
我做了如下完整的程序。这为您提供了投入正常工作。

 公共类堆排序{私有静态诠释N;私有静态无效掉期（INT [] A，int类型的，INT B）
{
    INT TMP = A [A];
    A [A] = A [B]。
    A [B] = tmp目录;
}私有静态无效插入（INT [] A，int i）以
{
    INT左= I * 2;
    INT右=左+ 1;
    INT最大= I;    如果（左＆LT; = N＆放大器;＆安培; A [左]＆gt;一种由[i]）{
        最大=左;
    }
    如果（右LT; = N＆放大器;＆安培; A [右]＆gt;将[MAX]）{
        MAX =权利;
    }
    如果（最大值！=ⅰ）{
        掉期（A，I，最大值）;
        插入（A，最大值）;
    }
}公共静态无效堆排序（INT [] A）
{
    N =则为a.length  -  1;    的for（int i = N / 2; I＆GT; = 0;我 - ）
        插入（A，I）;    的for（int i = N; I＆GT; 0;我 - ）{
        掉期（A，0，I）;
        N--;
        插入（A，0）;
    }
}公共静态无效的主要（字串[] args）{
    INT [] A = INT新[] {19，6，28，1，0};
    INT [B =新INT [] {1，2，4，8，9，0};
    的System.out.println（java.util.Arrays.toString（A））;
    的System.out.println（java.util.Arrays.toString（B））;
    堆排序（A）;
    堆排序（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]
 

I'm attempting to write a heapsort method in java but it's not working exactly as I want it to:

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));
    }
}

It works with some arrays however arrays like 9, 2, 8, 1, 4 will get sorted into 1, 4, 2, 8, 9. So why isn't it sorting the array in the correct way?

解决方案

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

Try this and see. I have made the complete program as below. This works fine for input you provided.

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));
}

}

Here is the output.

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

这篇关于这有什么错我的堆排序code？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！