快速排序平均時間複雜度為 O(n log n),但若輸入是已排序或接近排序好的陣列,卻會退化到 O(n²)。解法之一是引入「隨機化」:在每次分割前,隨機挑一個元素與基準元素交換,讓主元的選取擺脫輸入排列的影響,從而穩定維持平均 O(n log n)。
/***************************
* split:分割函式
* 輸入:array[low...high]
* 輸出:基準元素所在的新位置
***************************/
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; }
}
}
var temp = array[low]; array[low] = array[i]; array[i] = temp;
return i;
}
/***************************
* rquicksort:隨機化快速排序
***************************/
function rquicksort(array, low, high) {
if(low < high) {
// 隨機選主元並與 low 交換
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 之間隨機取一個索引 v,把 A[v] 與 A[low] 交換,之後照原本的 quicksort 邏輯繼續。這一步放寬了「所有排列機率相同」的假設,讓即使遇到近乎有序或已排序的輸入,也能保有良好的平均表現。