快速排序是公認高效的排序演算法,平均時間複雜度為 O(n log n)。但它有一個隱藏的弱點:當輸入陣列已經排序或接近有序時,效能會退化到 O(n²)。要解決這個問題,一個漂亮的做法就是引入「隨機化」。
傳統快速排序會固定挑選區間的第一個元素作為主元(pivot)。若資料恰好有序,每次分割都極不平衡,效率自然低落。隨機化快速排序的巧思在於:在區間 [low…high] 中隨機挑選一個索引 v,將 A[v] 與 A[low] 交換後再進行分割。這一步放寬了「輸入排列機率相同」的假設,讓平均效能穩定保持在 O(n log n),而這層預處理僅需 O(n) 時間即可完成。
/****************************************
算法:split
輸入:數組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 <= 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]
輸出:按非降序排列數組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);
parseInt(Math.random()*(high-low+1) + low) 這行的作用,是返回一個介於 low 與 high 之間的隨機整數作為主元索引。正是這個看似微小的改動,讓快速排序擺脫了對輸入資料分布的依賴,獲得更穩定可靠的表現。