JS實現隨機化快速排序的實例代碼

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

+

low)返回壹個在low和high之間的數。

復制代碼

代碼如下:　　

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

算法：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);