jsを使ってクイックソートを実装する方法

クイックソートは、実際に最もよく使用されるソートアルゴリズムでもあり、高速かつ効率的です。名前のとおり、クイック ソートは最適な並べ替えアルゴリズムです。

1) アルゴリズム原理

クイックソートの基本的な考え方: 1 回のソートパスでソート対象のレコードを 2 つの独立した部分に分離し、レコードの 1 つの部分のキーワードを分離します。他の部分のキーワードよりも優れている場合は、レコードのこれら 2 つの部分を別々にソートし続けて、シーケンス全体の順序付けを実現できます。

2) アルゴリズムの説明

クイックソートは、分割統治法を使用して文字列 (リスト) を 2 つのサブリスト (サブリスト) に分割します。具体的なアルゴリズムは次のように説明されます。

配列から「ピボット」と呼ばれる要素を選択します。

すべての要素がピボット値より小さくなるように配列を並べ替えます。これをベースの前に配置し、ベースの値より大きい要素はすべてベースの後ろに配置します (同じ番号をどちらの側にも配置できます)。このパーティションが終了すると、塩基はシーケンスの途中になります。これはパーティション操作と呼ばれます。

ベースライン値より小さい要素の部分配列と、ベースライン値より大きい要素の部分配列を再帰的に並べ替えます。

3) JavaScript コードの実装

function paritition(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}
function quickSort(arr, low, high) {
  if (low < high) {
    let pivot = paritition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
  }
  return arr;
}
  var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];    
  console.log(quickSort(arr,0,arr.length-1));

4) アルゴリズム分析

最良の場合: T(n) = O(nlogn) )
最悪のシナリオ: T(n) = O(n^2)
平均的なケース: T(n) = O(nlogn)

上位 10 のアルゴリズムのリスト:

1.JavaScript を使用して、トップ 10 のアルゴリズム 従来の並べ替えアルゴリズム - バブル ソート

2.JavaScript を使用してトップ 10 の古典的な並べ替えアルゴリズムを実装します - 選択ソート

3. JavaScript を使用してトップ 10 を実装します。古典的な並べ替えアルゴリズム -- 並べ替えの挿入

以上がjsを使ってクイックソートを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。