算法的平均时间复杂度为O(nlogn) 但是当输入是已经排序的数组或几乎排好序的输入 时间复杂度却为O(n^ ) 为解决这一问题并保证平均时间复杂度为O(nlogn)的方法是引入预处理步骤 它惟一的目的是改变元素的顺序使之随机排序 这种预处理步骤可在O(n)时间内运行 能够起到同样作用的另一种简单方法是在算法中引入一个随机元素 这可以通过随机地选择拆分元素的主元来实现 随机选择主元的结果放宽了关于输入元素的所有排列的可能性相同的步骤 引入这一步来修正原先的快速排序 可得到下面所示的随机化快速排序 新算法只是在区间[low…high]中一致随机地选择一个索引v 并将A[v]和A[low]交换 然后按照原来的快速排序算法继续 这里 parseInt(Math random()*(high low+ ) + low)返回一个在low和high之间的数
/****************************************
算法 split
输入 数组A[low high]
输出
若有必要 输出按上述描述的重新排列的数组A
划分元素A[low]的新位置w
****************************************/
function split(array low high) {
var i = low
var x = array[low]
for(var j = low + j <= highj++) {
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(Math random()*(high low+ ) + 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 array length )
lishixinzhi/Article/program/Java/JSP/201311/20538算法的平均时间复杂度为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)
