JS はヒルソートを実装します

この記事では主に JS での Hill ソートの実装を紹介します。これは必要な友人に参考にしていただけると思います。

ヒル ソートは基本的には挿入ソートですが、一連の操作を実行します。この最適化により、元の時間計算量が O(n^2) から O(nlogn) に減少します。

基本的な考え方

ヒルソートは、配列を一定の間隔でグループ化し、次に各グループで挿入ソートを実行し、その後徐々に間隔を減らし、間隔が 1 になるまで各グループで挿入ソートを実行します。挿入ソートを行ったら終了。

それでは、間隔をどれくらいの大きさにすべきか、そしてそれをどのように短縮するかが問題になります。通常、最初の間隔をシーケンスの長さの半分 (gap = length/2) とし、gap = gap/2 の形式で短縮します。プロセス全体を以下に詳しく説明します。

元の配列配列は以下の通りです:

まず、間隔をgap = length/2 = 4として取り、配列を以下の4つのグループに分割し、グループごとに挿入ソートを実装します。

まず一度ソートして、小さい要素の各グループを相対的に前の位置に移動させています（この状態をnソートと呼ぶことができます。つまり、グループ化がnをギャップとして順序付けされていると考えられます）。配列は、次のソートにさらに役立つ可能性があります。次に、グループ化を続けます (gap = gap/2 = 2)。グループごとに挿入ソートを実装します。

配列のグループ化を続けます (gap = gap/2 = 1)。つまり、すべての要素がグループを形成します。挿入ソートが完了しました アルゴリズム:

コード実装

// shellSort
function shellSort(arr) {
  for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
    // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
    for(let i = gap; i  0; j -= gap) {
        if(temp >= arr[j-gap]) {
          break;
        }
        arr[j] = arr[j-gap];
      }
      arr[j] = temp;
    }
  }
  return arr;
}

// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
alert(shellSort(arr));

ログイン後にコピー

Jquery はデジタル スクロール効果を実現するための読み込み遷移マスク

vue を追加します

以上がJS はヒルソートを実装しますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。