2

今日、ヒープソートの2つの異なる実装を作成しましたが、どちらも同じ結果をもたらしました。

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

ここで、このページでコードを確認しました。そして、私の実装の1つは擬似コードが示唆するものとまったく同じであると信じていますが、もう1つはJava実装の1つと非常に似ています。

私が実際に2つの異なるバージョンを作成し、それらを見つけた実装と照合したという事実を強調したいと思います。だから私は今本当に困惑しています！私はデバッガーでそれを数回ステップスルーしました-しかし、おそらく途中で何かを持っている必要がありますか？リストをループして内容を出力するデバッグ関数も作成しましたSystem.out.println()が、それでも大したことはありませんでした。

アルゴリズムはリストで機能しています-そして私はこの段階でそれを最適化するために何もしていません。現時点では、これはほんの少しの実験にすぎません。私はQuickSort、BubbleSort、Insertion Sortの実装を行っていますが、これは私を困惑させました！

私の最初の実装は以下のとおりです。

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で要点としてそれらを見ることができます：- 実装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()(または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){

このループは while でのみ実行する必要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);

は不必要です。常に swaptであるため、その行に到達すると、要素 at はi-1既に ですt。

于 2012-11-04T00:54:15.243 に答える