java - 堆排序工作 99%

Question

想知道我是否可以在堆排序实现方面获得一些快速帮助。我让它工作和排序很好，但在输出中它总是排序除了第一个数字。这可能只是某处的检查，但我已经检查了我的代码并尝试更改值，但没有产生我需要的结果。对我哪里出错有什么建议吗？这是我的源代码：

code removed, problem was solved!

多谢你们！

Answer 1

private static void movedown(double [] a, int k, int c) {
    while (2*k <= c-1) {
        int j = 2*k+1;
        if (j <= c-1 && less(a[j], a[j+1])) j++;
        if (!less(a[k], a[j])) break;
        exch(a, k, j);
        k = j;
    }
}

public static void heapsort(double [] a, int count) {
    for (int k = count/2; k >= 0; k--)
        movedown(a, k, count);
    while (count >= 1) {
        exch(a, 0, count--);
        movedown(a, 0, count);
    }
}

我已经修复了您的错误并在我的机器上对其进行了测试。它应该工作。这两种方法只有几个小改动。

总结一下你没有做对的事情：

1. 在heapsort方法中，count您传入的是从零开始的索引。但是，当您构建堆时，您只循环到k = 1，即再进行一次迭代。

2. 在movedown方法中，您应该知道左子索引是2*k+1，而右子索引是2*k+2。

您没有与您的索引选择保持一致（即，基于 0 与基于 1）导致了我猜的错误。