JS Hill ソート アルゴリズムについて (詳細なチュートリアル)

この記事では、JS ソート アルゴリズムのヒル ソートとクイック ソートの実装方法を主に紹介し、サンプルの形式でヒル ソートとクイック ソートの JavaScript 実装テクニックを分析します。この記事の例では、JS ソート アルゴリズム ヒル ソートとクイック ソートの実装方法について説明します。参考のために皆さんと共有してください。詳細は次のとおりです:

ヒルソート: 間隔シーケンスを定義します(例: 5、3、1)。初めて処理されるときは、間隔 5 ですべての要素が処理され、次回は間隔 3 で処理され、最後に処理されるときは間隔 1 で要素が処理されます。つまり、隣接する要素は標準の挿入ソートを実行します。

最後の処理の開始時に、ほとんどの要素は正しい位置にあり、アルゴリズムは多くの要素を交換する必要がなく、要素を挿入するよりも高度です。

時間計算量

O(n*logn)

function shellSort(){
  var N=arr.length;
  var h=1;
  while(h<N/3){
    h=3*h+1;//设置间隔
  }
  while(h>=1){
    for(var i=h; i<N; i++){
      for(j=i; j>=h && arr[j]<arr[j-h]; j-=h){
        swap(arr, j, j-h);
      }
    }
    h=(h-1)/3;
  }
}
function swap(array, i, j){//两个数调换
  var temp =array[j];
  array[j]=array[i];
  array[i]=temp;
}

クイックソート: データをより小さな要素とより大きな要素を含む異なるサブシーケンスに再帰的に分解し、すべてのデータが整うまでこの手順を繰り返します。

ベンチマーク値を選択し、ベンチマーク値より小さい値を配列に入れます。ベンチマーク値より大きいものは配列に配置されます。

時間の複雑さ

O(n*logn)

function quickSort(arr){
  if(arr.length==0){
    return [];
  }
  var left=[];
  var right=[];
  var p=arr[0];
  for(var i=1; i<arr.length; i++){
    if(arr[i]<p){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(p,quickSort(right));
}

以上は皆さんのためにまとめたもので、将来皆さんのお役に立てれば幸いです。

関連記事:

JavaScriptのnull値とfalse値について

Webpackでの自動構築について(詳細チュートリアル)

WeChatアプレットに画像アップロードなどの一連の機能を実装する方法

ユニバーサルフロントエンドデータシミュレーションフレームワークを構築する方法 (詳細なチュートリアル)

以上がJS Hill ソート アルゴリズムについて (詳細なチュートリアル)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。