算法的平均時(shí)間復(fù)雜度為O(nlogn)。但是當(dāng)輸入是已經(jīng)排序的數(shù)組或幾乎排好序的輸入，時(shí)間復(fù)雜度卻為O(n^2)。為解決這一問題并保證平均時(shí)間復(fù)雜度為O(nlogn)的方法是引入預(yù)處理步驟，它惟一的目的是改變元素的順序使之隨機(jī)排序。這種預(yù)處理步驟可在O(n)時(shí)間內(nèi)運(yùn)行。能夠起到同樣作用的另一種簡單方法是在算法中引入一個(gè)隨機(jī)元素，這可以通過隨機(jī)地選擇拆分元素的主元來實(shí)現(xiàn)。隨機(jī)選擇主元的結(jié)果放寬了關(guān)于輸入元素的所有排列的可能性相同的步驟。引入這一步來修正原先的快速排序，可得到下面所示的隨機(jī)化快速排序。新算法只是在區(qū)間[low…h(huán)igh]中一致隨機(jī)地選擇一個(gè)索引v，并將A[v]和A[low]交換，然后按照原來的快速排序算法繼續(xù)。這里，parseInt(Math.random()*(high-low+1) + low)返回一個(gè)在low和high之間的數(shù)。
/****************************************
算法：split
輸入：數(shù)組A[low...high]
輸出：
1.若有必要，輸出按上述描述的重新排列的數(shù)組A;
2.劃分元素A[low]的新位置w;
****************************************/
function split(array, low, high) {
var i = low;
var x = array[low];
for(var j = low + 1; j <= high; j++) {
if(array[j] <= x) {
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]
輸出：按非降序排列數(shù)組A[0...n-1]
rquicksort(A, 0, n-1);
****************************************/
function rquicksort(array, low, high) {
if(low < high) {
/******隨機(jī)化拆分元素的主元*******/
var v = parseInt(Math.random()*(high-low+1) + low);
var tmp = array[low];
array[low] = array[v];
array[v] = tmp;
/******隨機(jī)化拆分元素的主元*******/
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);
