Shell のソートは、非常に「魔法の」ソート アルゴリズムです。それが「魔法」と呼ばれるのは、その性能が何であるかを誰も明確に説明できないためです。 DLによるヒルソート。シェルは 1959 年に提案されたことにちなんで名付けられました。 1962 年に C. A. R. Hoare がクイック ソートを提案して以来、より簡単なクイック ソートが一般的に使用されています。しかし、多くの数学者は今もヒルソートの最適な複雑さを見つけるために精力的に研究を続けています。普通のプログラマーとして、私たちはヒルのアイデアから学ぶことができます。
ちなみに、ヒルソートが登場する前は、コンピュータ業界では「ソートアルゴリズムはO(n2)を突破できない」という共通認識がありました。ヒルソートの登場によりこの呪縛は打ち破られ、やがてクイックソートなどのアルゴリズムが次々と登場しました。その意味で、ヒルソーティングは私たちを新しい時代へと導きます。
アルゴリズムの概要/アイデア
ヒル ソートの提案は主に次の 2 つの点に基づいています:
1. 配列が基本的に順序付けされている場合、挿入ソート アルゴリズムはおよそ O(n) の複雑さに達することができ、非常に効率的です。
2. ただし、挿入ソートは一度に 1 ビットしかデータを移動できないため、配列が大きく、基本的に順序付けされていない場合、パフォーマンスが急速に低下します。
これに基づいて、グループ化された挿入ソート方法を使用できます。具体的な方法は次のとおりです: (例として 16 個の要素の配列を使用します)
1. 1 より大きい増分デルタを選択し、配列から を押します。この増分により、直接挿入ソートのサブ配列が選択されます。たとえば、選択した増分が 5 の場合、インデックス 0、5、10、および 15 を持つ要素が並べ替えられます。
2. 増分デルタを保持し、1 ラウンドが完了するまで直接挿入ソートのために最初の要素を順番に移動します。上の例では、配列 [1, 6, 11]、[2, 7, 12]、[3, 8, 13]、[4, 9, 14] が順番にソートされます。
3. 増分を減らし、増分が 1 になるまで上記のプロセスを繰り返します。明らかに、最後は直接挿入ソートです。
4. 並べ替えが完了しました。
上記からわかるように、増分は常に減少しているため、ヒルソートは「縮小増分ソート」とも呼ばれます。
コード実装
package sort;
public class ShellSortTest {
public static int count = 0;
public static void main(String[] args) {
int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
print(data);
shellSort(data);
print(data);
}
public static void shellSort(int[] data) {
// 计算出最大的h值
int h = 1;
while (h <= data.length / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (int i = h; i < data.length; i += h) {
if (data[i] < data[i - h]) {
int tmp = data[i];
int j = i - h;
while (j >= 0 && data[j] > tmp) {
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
print(data);
}
}
// 计算出下一个h值
h = (h - 1) / 3;
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}実行結果:
5 3 6 2 1 9 4 8 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 9 8 7 1 2 3 4 5 6 8 9 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
アルゴリズムのパフォーマンス/複雑さ
ヒルソートの増分シーケンスは任意に選択できます。必要な唯一の条件は、最後のものが 1 であることです (1 ずつ順序付けされる必要があるため)。 。ただし、シーケンスの選択が異なると、アルゴリズムのパフォーマンスに大きな影響を与えます。上記のコードは 2 つの増分を示しています。
覚えておいてください: インクリメンタル シーケンス内の 2 つの要素ごとに 1 以外の共通因数を持たないことが最善です。 (明らかに、シーケンスを 4 で並べ替えてから 2 で並べ替えることはあまり意味がありません)。
ここでは、一般的なデルタ シーケンスをいくつか示します。
最初の増分は、ドナルド シェルによって当初提案された増分であり、1 になるまで半分に減らされます。研究によると、ヒル インクリメントを使用しても、時間計算量は依然として O(n2) です。
2 番目の増分 Hibbard: {1, 3, ..., 2^k-1}。この増分シーケンスの時間計算量は約 O(n^1.5) です。
3 番目のインクリメント Sedgewick インクリメント: (1, 5, 19, 41, 109,...)、生成されるシーケンスは 9*4^i - 9*2^i + 1 または 4^i - 3*2^ のいずれかですi+1。
アルゴリズムの安定性
挿入ソートが安定したアルゴリズムであることは誰もが知っています。ただし、シェル ソートは複数の挿入プロセスです。 1 回の挿入では、同じ要素の順序が移動しないことを保証できますが、複数の挿入では、同じ要素が異なる挿入ラウンドで移動する可能性があり、最終的には安定性が損なわれるため、シェルのソート アルゴリズムは安定しません。 。
アルゴリズムの適用シナリオ
シェルソートは高速ですが、所詮は挿入ソートであり、新星であるクイックソーティングO(n㏒n)ほど高速ではありません。シェルソートは、大量のデータを扱う場合には適切なアルゴリズムではありません。ただし、小規模から中規模のデータにはまったく問題ありません。
Hill ソート アルゴリズムの詳細な説明と関連する Java コード実装関連の記事については、PHP 中国語 Web サイトに注目してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
