1

私はこのようなアプリケーションにシェルソートアルゴリズムを実装しました：

shell: function() {
    var list = anada.vars.$list;
    for (i = 0; i < list.length; i++) {
        list[i] = parseInt(list[i], 10);
    }
    var n = list.length;
    var increment = Math.floor(n / 2);
    var i;        

    while (increment > 0) {
        for (i = increment; i < n; i++) {
            var temp = list[i];
            var j = i;
            var affectedOne = j;
            var affectedTwo;
            while (j >= increment && list[j - increment] > temp) {
                list[j] = list[j - increment];
                j -= increment;
            }
            list[j] = temp;
            var rows = '<tr>';
            for (counter = 0; counter < n; counter++) {
                if (counter > j - increment && counter < i + 1 && counter % increment == 0) {
                    rows += '<td class="affected">' + list[counter];
                } else {
                    rows += '<td>' + list[counter];
                }
            }
            anada.vars.$elements.push(rows);
        }
        increment = Math.floor(increment / 2);
        var row = '<tr>';
        $.each(list, function(n, val) {
            row += '<td class="iteration">' + val;
        });
        anada.vars.$elements.push(row);

    }
    $('.result-content').find('table').empty();
    $.each(anada.vars.$elements, function(n, val) {
        $('.result-content').find('table').append(val);
    });
    anada.vars.$elements = [];

},

問題は次のようなものです。

  1. 並べ替えの最初の部分は「21」のみを強調表示します。15と21はエントリからの位置を変更しなかったため、強調表示してはなりません。リストエントリは15,14,0,34,2,44,21,6でした。 、7、12、5、34、20。

インデックス0がインデックス7よりも大きい場合（リストの総数の半分+ 1）、位置が変わります。

これはペアリングです：

最初の反復：15-21、14-6、0-7、34-12、2-5、44-34、6-20

私が強調したいのは、位置が変更されたものだけです。

並べ替えの最初の部分 何度か繰り返した後、終了部分は挿入ソートのようになります

私の間違いは何ですか。

4

1 に答える 1

1

計算してみましょう。値iは、要素を逆方向にスワップし始めたインデックスを表します。値jは、その要素が最終的に到達した場所でありincrement、ステップ サイズを表します。

position の要素を考えてみましょうcounter。次のすべてが true の場合、移動した要素と交換されました。

  • counterjは、の倍数から進むステップ数ですincrement。つまり、counter >= j && counter - j % increment == 0.

  • counterスタート地点を過ぎていません。つまり、counter <= i.

  • 少なくとも 1 つの要素が移動しました。つまり、i != j.

これをまとめると、次の条件が得られます。

if (i != j && counter <= i && counter >= j && counter - j % increment == 0) {
    // Element was swapped
} else {
    // Element was not swapped
}

あなたがチェックしている状態はこれに近いですが、いくつかの off-by-one エラーがありj、mod を実行するときにシフトするのを忘れています。これを試して、問題が解決するかどうかを確認してください。

于 2015-08-26T17:27:14.413 に答える