java - (Java) Heapsort - 实现不对半元素进行排序？

Question

我今天写了两个不同的堆排序实现，都给了我相同的结果:

Object i: 18
Object i: 11
Object i: 10
Object i: 9
Object i: 8
Object i: 3
Object i: 7
Object i: 1
Object i: 4

现在我已经用这个页面检查了我的代码 here ;并相信我的一个实现与伪代码所建议的完全相同，而另一个与其中一个 Java 实现非常相似。

我想强调一个事实，我实际上写了两个不同的版本，并根据我能找到的实现对它们进行了检查!所以我现在真的很难过!我已经用调试器逐步完成了几次 - 但可能一定有一些东西？我什至制作了一个调试功能，它只是循环遍历列表并使用 System.out.println() 输出内容 - 但这仍然没有太大帮助!

该算法正在一个列表上运行 - 而我在这个阶段什么都没有对其进行优化；目前这只是一个实验。我有 QuickSort、BubbleSort 和插入排序的有效实现 - 但这个让我很困惑!

我的第一个实现如下:

public static List<Integer> execSort(List<Integer> s) {

    int n = (s.size()-1);
    Integer t;

    for(int i = n/2; i>0; i--){
        s = downheap(s, i, n);
    }

    while(n >= 1){
        t= s.remove(0);
        s.add(0, s.remove(n-1));
        s.add(n-1, t);

        n--;
        s = downheap(s, 1, n);
    } 

    return s;
}


public static List<Integer> downheap(List<Integer> s, int i, int n){
    Integer t = s.get(i-1);
    int j;

    while( i <= n/2 ){  
        j = i*2;

        if( (j<n) && (s.get(j-1) < s.get(j)))
            j++;

        if( t >= s.get(j-1)){
            break;
        } else {
            /* Swap them, without using a third variable 
                        - although with all the get()/set() methods
                        it would be better to have a third one, doh! */ 
            s.set(i-1, (s.get(i-1) + s.get(j-1)));
            s.set(j-1, (s.get(i-1) - s.get(j-1)));
            s.set(i-1, (s.get(i-1) - s.get(j-1)));

            i=j;
        }
    }

    s.set(i-1, t);
    return s;
}

你也可以在 Github 上看到它们作为 Gists:- Implementation 1- Implementation 2

关于为什么有些元素不想排序的任何想法？!我知道这个实现将是次优的，在 List<> 上工作是' 将成为最好的数据结构，我可能应该考虑使用原始数据类型而不是(ab)使用自动装箱......但那是另一篇文章!在我尝试和改进它之前，我只想要一个工作版本；)

Answer 1

在要点中(你不小心将两者链接到了同一个)，你有一些错别字

public static List<Integer> execSort(List<Integer> s) {

    int start = (s.size()/2)-1;
    int end = s.size()-1;

    while( start >= 0){
        s = sift(s, start, end);

sift将计数作为最后一个参数，而不是最后一个索引，因此参数应该是 s.size() (或 end+1 )而不是 end .

public static List<Integer> sift(List<Integer> s, int start, int count){

    int root = start;

    while( ((root*2)+1) < 2 ){

那一定是while(root*2+1 < count) ，而不是 < 2 .

在你这里的代码中，你有部分相同的问题(我怀疑是由奇怪的索引策略引起的):

    for(int i = n/2; i>0; i--){
        s = downheap(s, i, n);

因为你总是get(i-1)分别j-1在 downheap ，你需要一个上限 s.size()或 n+1在构建初始堆时。

    }

    while(n >= 1){

这个循环应该只在 n > 1 时运行，否则您将把最小的元素交换错位。

        t= s.remove(0);
        s.add(0, s.remove(n-1));
        s.add(n-1, t);

旧根必须放在最后一个地方，即n , 不是 n-1 , s.add(n,t) .

        n--;
        s = downheap(s, 1, n);
    } 

在downheap , 最后的

    s.set(i-1, t);

是多余的，你总是交换t ，所以当到达该行时，位于 i-1 的元素已经是t .