Javascriptクイックソートアルゴリズムを詳しく解説_基礎知識

クイックソートはバブルソートを改良したものです。 1 パスの並べ替えにより、並べ替えるデータを 2 つの独立した部分に分割します。次に、この方法を使用して、データの 2 つの部分全体をそれぞれすばやく並べ替えます。ソート処理は再帰的に進むことができ、最終的にデータ全体が順序付けられたシーケンスになります。

ソートする配列が A[0]...A[N-1] であると仮定します。まず、ベンチマーク データとしてデータ (通常は配列の最初の数値) をランダムに選択し、それより小さいすべての数値を選択します。それをその前に置き、それより大きいすべての数字をその後ろに置くこのプロセスは、ワンパス クイック ソートと呼ばれます。クイックソートは安定したソートアルゴリズムではないことに注意してください。つまり、複数の同一の値の相対位置がアルゴリズムの終了時に変わる可能性があります。
ワンパスクイックソートのアルゴリズムは次のとおりです:
1) ソート開始時に 2 つの変数を low=0、high=N-1 に設定します。 2) 最初の配列要素を参照データとして使用し、それをbase、つまりbase=A[0]に割り当てます。 3) 高から前方へ検索、つまり後方から前方へ検索 (高--)、ベースより小さい最初の値 A[高] を見つけ、A[高] と A[低] を交換します。 4) ローから後方に検索します。つまり、前から後ろ (ロー) に検索し、ベースより大きい最初の A[low] を見つけ、A[low] と A[high] を交換します。 5) 低 = 高になるまでステップ 3 と 4 を繰り返します。

コードをコピーします

コードは次のとおりです: 関数パーティション(要素、低、高){ //デフォルトでは、左側の最初の要素がベース要素として使用されます varbase=elements[low];

while(低 //ベース要素よりも小さい要素が見つかるまで後ろから前に検索し、それを交換します
While(low < high && elements[high] >= Base) high--;
var swap1=要素[低];要素[低]=要素[高];要素[高]=swap1;
//ベース要素より大きい要素が見つかるまで前から後ろに検索し、それを交換します
While(low < high && elements[low] <= Base) low ;
var swap2=要素[低];要素[低]=要素[高];要素[高]=swap2;
}
//参照要素の位置をシーケンスの分割位置として返す
ローに戻ります;
}
関数 sort(要素、低、高){
if(低 // シーケンスを 2 つに分割し、分割位置の前後のシーケンスに分割します。前者のシーケンスは分割位置より小さい値、後者のシーケンスは分割位置より大きい値になります。 varpartitionPos=パーティション(要素、低、高);
//前のシーケンスを再帰的に並べ替え続けます
ソート(要素, 0, パーティション位置-1);
//後続のシーケンスを再帰的にソートし続けます
Sort(要素、partitionPos 1、高);
}
}
var 要素 = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('before: ' 要素);
sort(要素, 0, 要素.長さ-1);
console.log(' 後: ' 要素);



効率:

時間計算量: 最良: O(nlog2n)、最悪: O(n^2)、平均: O(nlog2n)。
空間複雑度: O(nlog2n)。

安定性: 不安定です。