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 .