JS實現隨機化快速排序

　　算法的平均時間復雜度為O(nlogn)但是當輸入是已經排序的數組或幾乎排好序的輸入時間復雜度卻為O(n^)為解決這一問題並保證平均時間復雜度為O(nlogn)的方法是引入預處理步驟它惟一的目的是改變元素的順序使之隨機排序這種預處理步驟可在O(n)時間內運行能夠起到同樣作用的另一種簡單方法是在算法中引入一個隨機元素這可以通過隨機地選擇拆分元素的主元來實現隨機選擇主元的結果放寬了關於輸入元素的所有排列的可能性相同的步驟引入這一步來修正原先的快速排序可得到下面所示的隨機化快速排序新算法只是在區間[low…high]中一致隨機地選擇一個索引v並將A[v]和A[low]交換然後按照原來的快速排序算法繼續這裡parseInt(Mathrandom()*(highlow+) + low)返回一個在low和high之間的數

　　/****************************************

　　算法split

　　輸入數組A[lowhigh]

　　輸出

　　若有必要輸出按上述描述的重新排列的數組A;

　　劃分元素A[low]的新位置w;

　　****************************************/

　　function split(array low high) {

　　var i = low;

　　var x = array[low];

　　for(var j = low + ; 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[n]

　　輸出按非降序排列數組A[n]

　　rquicksort(A n);

　　****************************************/

　　function rquicksort(array low high) {

　　if(low < high) {

　　/******隨機化拆分元素的主元*******/

　　var v = parseInt(Mathrandom()*(highlow+) + low);

　　var tmp = array[low];

　　array[low] = array[v];

　　array[v] = tmp;

　　/******隨機化拆分元素的主元*******/

　　var w = split(array low high);

　　rquicksort(array low w );

　　rquicksort(array w + high);

　　return array;

　　}

　　}

　　var array = [ ];

　　array = rquicksort(array arraylength);

　　consolelog(array);

From:http://tw.wingwit.com/Article/program/Java/JSP/201311/20538.html