DIV CSS 佈局教程網

用 JavaScript 實作隨機化快速排序演算法
編輯:關於JavaScript     

快速排序是公認高效的排序演算法,平均時間複雜度為 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 之間的隨機整數作為主元索引。正是這個看似微小的改動,讓快速排序擺脫了對輸入資料分布的依賴,獲得更穩定可靠的表現。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved