java - 二进制堆排序的代码

Question

我正在练习用伪代码编写代码。我在查看算法简介文本时发现了这一点。然而，我确信我的代码完全符合伪代码；它没有输出我想要的东西。该代码是一个二元堆排序。该代码没有对我的输入进行排序，而是将我的输入原样返回为输出。我对这个问题的想法存在于 build 方法中，我将 Math.floor() 转换为 int。这是我第一次使用 floor()，所以我相信我缺乏理解是问题所在。我相信我返回的是 heapsize/2 的最低近似值，因此我可以对我的Binary Heap 进行分支。但我的编码是这样吗？

public class tester
{
public static void heapsort(int[] a)
{

    build(a);

    for (int i = a.length - 1; i >= 1; i--)
    {
        swap(a, 0, i);
        int heapsize = a.length - 1;
        heapify(a,0);
    }
}

public static void build(int[] a)
{
    int heapsize = a.length;
    int fl = (int) Math.floor((heapsize)/2);
    for (int i = fl; i >= 0; i--)
    {
        heapify(a, i);
    }
}

public static void heapify(int[] a, int root)
{
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    int heapsize = a.length;
    int largest;

    if ( (left < heapsize) && (a[left] > a[root]))
    {
        largest = left;
    }
    else
    {
        largest = root;
    }
    if ( (right < heapsize) && (a[right] > a[largest]))
    {
        largest = right;
    }
    if (largest != root)
    {
        swap(a, a[root], a[largest]);
        heapify(a, largest);
    }

}

public static void swap(int[] a, int x, int y)
{
    int tmp;
    tmp = a[x];
    a[x] = a[y];
    a[y] = tmp;
}

public static void main(String[] args)
{
    int[] a = new int[args.length];
    for (int i = 0; i < args.length; i++)
    {
        a[i] = Integer.parseInt(args[i]);
    }
    heapsort(a);
    for (int i : a)
    {
            System.out.println(i);
        }
    }
}    

Answer 1

您的交换方法在 Java 中不起作用，因为您只能按值传递基元，而不能按引用传递基元。您可以像这样修改方法:

public static void swap(int[] a, int i, int j)
{
    int tmp;
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

这将被称为

    swap(a, 0, i);

而不是

    swap(a[0], a[i]);

并且会正确交换数组中的两个数字。