Javaソートアルゴリズムの概要（IV）：シェルソート

シェルソート（縮小増分法）は挿入型ソートに属し、順序付けられていないシーケンス全体をいくつかの小さなサブシーケンスに分割し、それらを個別に挿入してソートします。シェルソートは安定しておらず、追加スペースは O(1)、時間計算量は O(N*(logN)^2) です。最悪の場合の実行効率は、平均的な場合の実行効率とそれほど変わりません。

基本的な考え方:

まず、最初の増分として n より小さい整数 d1 を取り、ファイル内のすべてのレコードを d1 グループに分割します。距離が d1 の倍数であるすべてのレコードは同じグループに配置されます。まず、各グループ内で直接挿入ソートを実行します。次に、2 番目の増分 d2<d1 を取り、増分 dt=1 (dt<dt-l<…<d2<d1) になるまで、つまりすべてのレコードが同じグループに配置されて直接挿入ソートが実行されるまで、上記のグループ化とソートを繰り返します。

コード実装:

パブリッククラステスト{
 public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // プリセットデータ配列
パブリック静的void main(String args[]) {
 int i; // ループカウント変数
int Index = a .length; // データインデックス変数
System.out.print("ソート前: ");
 ( i = 0 ; i <の場合 インデックス- 1; i++)
 System.out.printf("%3s ", a);
 System.out.println("");
 ShellSort(Index - 1); // ソートを選択
// ソートされた結果
System.out.print("ソート後: ");
 ( i = 0 ; i <の場合 インデックス- 1; i++)
 System.out.printf("%3s ", a);
 System.out.println("");
 }
パブリック静的void ShellSort(int Index) {
 int i, j, k; // ループカウント変数
int Temp; // 一時変数
boolean Change; // データが変更されたかどうか
int DataLength; // コレクションを分割する間隔の長さ
int ポインタ; // 処理する場所
DataLength = (int) Index / 2; // 初期収集間隔の長さ
while (DataLength != 0) // シーケンスはまだ分割できます
{
 // 各コレクションを処理する
for ( j = DataLength ; j <  インデックス; j++) {
変更= false ;
 Temp = a [j]; // 後で使用するためにData[j]の値を一時的に保存します
Pointer = j - DataLength; // 処理する位置を計算する
// コレクション内の値を比較して交換する
(Temp &lt;の間、   a [ポインタ] && ポインタ> = 0 && ポインタ< = インデックス) {
 a[ポインタ + データ長] = a[ポインタ];
 // 次に処理する位置を計算する
ポインタポインタ= ポインタ - データ長;
変更= true ;
 if (ポインタ&lt;   0 || ポインタ>インデックス)
壊す;
 }
 // 最後の値と交換
a[ポインタ + データ長] = Temp;
 if (変更) {
 // 現在のソート結果を出力します
System.out.print("ソート: ");
 ( k = 0 ; k &lt; )の場合 インデックス; k++)
 System.out.printf("%3s ", a[k]);
 System.out.println("");
 }
 }
 DataLength DataLength = DataLength / 2; // 次のセグメンテーションの間隔の長さを計算します
}
 }
 }

シェルソートでは、最悪のシナリオはほとんどありません。順方向、逆方向、ランダムな順序のいずれであっても、かかる時間はそれほど長くなく、追加のストレージは O(1) であり、これは非常に優れています。クイックソートとヒープソートを理解する前に、それは確かに良い選択です。これがお役に立てば幸いです。

【編集者のおすすめ】

1. Java オブジェクト インスタンスはいつ作成されますか?
2. C++ ソートに関する 4 つの古典的な講義: シェル ソート
3. Java Web アプリケーション開発におけるいくつかの概念の解釈