DIV CSS 佈局教程網

JS 實作隨機化快速排序(Randomized Quicksort)
編輯:JavaScript綜合知識     

快速排序平均時間複雜度是 O(n log n),但若輸入已經排序或接近排序,會退化到 O(n²)。解法很優雅:隨機挑選主元(pivot),讓任何輸入排列被視為等機率。

隨機化的作用

傳統快排取區間第一個元素當主元,遇到已排序資料時每次分割都極不平衡。隨機化版本在出發前先做一次 O(1) 的交換:在 [low, high] 之間隨機選一個索引 v,把 A[v] 和 A[low] 對調,之後照原本的邏輯繼續。就這麼一行,讓平均複雜度穩定回到 O(n log n)。

split:分割函式

/****************************************
算法:split
輸入:數組 A[low...high]
輸出:重新排列後的陣列,以及分割元素 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;
}

這裡用的是 Lomuto 分割法:i 指向「已知小於等於主元的區域」的右界,j 負責往前掃。迴圈結束後把主元換到 i 的位置,它就落在最終的正確排序位置上了。

rquicksort:遞迴主體

/****************************************
算法:rquicksort
輸入: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) 可以簡寫成 Math.floor(Math.random() * (high - low + 1)) + low,語意更清楚。

另外,資料量稍大時遞迴深度可能導致 stack 溢出。實務做法是:對較小區間(例如少於 10 個元素)改用插入排序,並先遞迴較小那一半、較大那一半用迴圈處理,即可把堆疊深度壓到 O(log n)。若只是要排序,原生 array.sort((a,b) => a-b) 已經是高度最佳化的實作,通常不必自己寫。

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