DIV CSS 佈局教程網

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

快速排序平均時間複雜度為 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 邏輯繼續。這一步放寬了「所有排列機率相同」的假設,讓即使遇到近乎有序或已排序的輸入,也能保有良好的平均表現。

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