2

我今天写了两种不同的 heapsort 实现，都给了我相同的结果：

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

现在我在这里用这个页面检查了我的代码；并相信我的一个实现与伪代码所建议的完全相同，而另一个与 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： -实施 1 -实施 2

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

4

1 回答 1

2

在要点中（您不小心将两者链接到同一个），您有一些错别字

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()(or 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)resp。j-1在 中，您需要或在构建初始堆时downheap的上限。s.size()n+1

    }

    while(n >= 1){

这个循环应该只运行 while n > 1，否则你会交换最小的元素。

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

旧根必须放在最后一个位置，即 place n，而不是n-1, s.add(n,t)。

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

中downheap，决赛

    s.set(i-1, t);

是多余的，你总是交换t，所以当到达那条线时，元素i-1已经是t。

于 2012-11-04T00:54:15.243 回答