JS_javascript スキルでランダム化されたクイックソートを実装するサンプルコード

アルゴリズムの平均時間計算量は O(nlogn) です。ただし、入力がソートされた配列またはほぼソートされた入力である場合、時間計算量は O(n^2) になります。この問題を解決し、平均時間計算量が O(nlogn) であることを保証するために、この方法では前処理ステップを導入します。このステップの唯一の目的は、要素の順序をランダムな順序に変更することです。この前処理ステップは O(n) 時間で実行できます。同じ効果を達成できるもう 1 つの簡単な方法は、アルゴリズムにランダムな要素を導入することです。これは、分割要素のピボットをランダムに選択することで実現できます。ピボットをランダムに選択した結果、入力要素のすべての順列が等しく発生する点までステップが緩和されます。このステップは、元のクイック ソートを変更するために導入され、以下に示すランダム化されたクイック ソートを取得できます。新しいアルゴリズムは、[low...high] の間隔でインデックス v をランダムに選択し、A[v] と A[low] を交換し、元のクイック ソート アルゴリズムに従って続行します。ここで、parseInt(Math.random()*(high-low 1) low) は、低値と高値の間の数値を返します。

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

/******************************************
アルゴリズム: 分割
入力:配列 A[low...high]
出力:
1. 必要に応じて、上記のように再配置された配列 A を出力します。
2. 要素 A[low] の新しい位置 w を除算します。 >******************************************/
function Split(array, low, high) {
var i = low;
var x = array[low];
for(var j = low 1; j if(array[j] i ;
if(i != j) {
var temp = array[i];
array[i] = array[ j];
array[j] = temp;
}
}
}
temp = array[low];
array[low] = array[i] ;
array[i] = temp;
return i;
}
/******************************************
アルゴリズム: rquicksort
入力: A [0...n-1]
出力: 配列 array A[0...n-1]
(非降順) rquicksort(A, 0, n-1);
* **************************************/
function rquicksort(array, low, high) {
if( low < high) {
/******分割要素のピボットをランダム化*****/
var v = parseInt(Math.random()*(high-low 1) low);
var tmp = array[low] ;
array[low] = array[v];
array[v] = tmp;
/******分割要素のピボットをランダム化*****/
var w = split(array, low, high);
rquicksort(array, low, w -1);
rquicksort(array, w 1, high);
return array;
}
}
var array = [33, 22, 11 , 88, 23, 32];
array = rquicksort(array, 0, array.length-1);
console.log(array);