JavaScript ソートアルゴリズムの 2 つの例 丘ソート_基礎知識

挿入ソートは、ほぼソートされたデータを操作する場合に非常に効率的です。つまり、線形ソートの効率を達成できます。
しかし、挿入ソートは一度に 1 ビットしかデータを移動できないため、一般に非効率的です。
ヒル ソートは、設計者のドナルド シェルにちなんで名付けられ、アルゴリズムは 1959 年に公開されました。一部の古い教科書や参考書では、このアルゴリズムにマレーネ・メッツナー・ノートンの名前が含まれるシェル・メッツナーという名前が付けられていましたが、メッツナー自身によると、「私はこのアルゴリズムのために何もしていません。私の名前はアルゴリズムに登場すべきではありません」とのことです。 >

ヒル ソートの基本的な考え方: まず最初の増分として n より小さい整数 d1 をとり、ファイル内のすべてのレコードを d1 グループに分割します。距離が d1 の倍数であるすべてのレコードは、同じグループに配置されます。まず各グループ内で直接挿入ソートを実行し、次に 2 番目の増分 d2

このメソッドは基本的にグループ化された挿入メソッドです。

例 1:

コードをコピーします コードは次のとおりです:

/**
* ヒル ソートは、降順増分ソート アルゴリズムとも呼ばれ、挿入ソートのより効率的かつ改良されたバージョンです。ヒルソートは不安定なソートアルゴリズムです。
*
* ヒル ソートは、挿入ソートの次の 2 つの特性に基づいた改良された方法を提案します。
*
* 挿入ソートは、ほぼ既にソート済みのデータを操作する場合に非常に効率的です。線形ソートの効率は達成できます
* しかし、挿入ソートは一度に 1 ビットしかデータを移動できないため、一般に非効率的です
*
*/

functionshellSort( list ) {
var gap = Math.floor( list.length / 2 );

while(gap > 0 ) {

for( i = ギャップ; i temp = list[i];

for( j = i; j >= ギャップ && list[ j - ギャップ ] > j -= ギャップ ) {
list[j] = list[j - ギャップ];
list[j] = temp;
}

ギャップ= Math.floor(gap / 2 );
}

return list;
};

// test
var arr = [2, 1, 3 , 12、5、66、23、87、15、32];

shellSort(arr);

例 2:

コードをコピーします コードは次のとおりです: