5

誰かが、Knuth シーケンスを使用する Java のシェルソートの簡単な作業サンプルを提供できますか? 私はインターネット上のいくつかの場所を見ましたが、私にとってうまくいく説明を見つけることができません. 概念レベルでシェルソートを理解しています-これは、ギャップが1に達するまで時間の経過とともに縮小するギャップで行われる挿入ソートであるため、本質的に挿入ソートです。ただし、Knuth シーケンスは (k * 3 - 1)/2 であり、最初のいくつかのギャップのリストは通常​​ [1、4、13、40、121.. など] として表されます。

私の質問は、これをどのように実装するのですか? 開始ギャップは実際には 1 ですか、それともソートされるリストのサイズよりも大きい直前にこのシーケンスによって生成された値ですか? ギャップが 1 から始まった場合、シェル ソートを正しく理解していると、目的が達成できなくなります。誰かがこれに光を当てることができますか？このことを理解するための重要な何かを見逃しているように感じます。

前もって感謝します。

4

2 に答える 2

5

遅い回答ですが、将来の見物人が怠惰すぎて他の回答からのリンクをたどったり、リンクが壊れたりした場合...

これは、Knuth アルゴリズムを実装して、最初のギャップ値と残りのギャップ値を降順で見つける方法です。

// Find initial gap.
gap = 1; 
while gap < arrayLength {
  gap = gap * 3 + 1;
}

// Perform the main sorting logic...

// Somewhere within code, at the end
// of the main sorting logic, find next
// descending gap value.
gap /= 3;

開始ギャップは 1 ではありません。これは、並べ替えられる配列の長さを超える前に計算された最後の最大数です。

下部の 3 ピースによる除算は、基本的に while ループで実行された計算の逆の順序で行われ、シーケンス内の次のギャップ値を降順で取得します。これは、メインの並べ替えロジックの最後に毎回行われます。

また、式は実際には (3^k - 1) / 2 であり、(3k - 1) / 2 ではありません。前者は正しいシーケンス (1、4、13、40、...) になり、後者は間違ったもの。

于 2019-07-15T01:26:07.313 に答える