算法的平均时间复杂度为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
从给定的数据中，随机抽出一项，这项的左边放所有比它小的，右边放比它大的，然后再分别这两边执行上述操作，采用的是递归的思想，总结出来就是 实现一层，分别给两边递归，设置好出口
function fastSort(array,head,tail){//考虑到给每个分区操作的时候都是在原有的数组中进行操作的，所以这里head,tail来确定分片的位置
/*生成随机项*/
var randomnum = Math.floor(ranDom(head,tail))
var random = array[randomnum]
/*将小于random的项放置在其左边 策略就是通过一个临时的数组来储存分好区的结果，再到原数组中替换*/
var arrayTemp = []
var unshiftHead = 0
for(var i = headi <= taili++){
if(array[i]<random){
arrayTemp.unshift(array[i])
unshiftHead++
}else if(array[i]>random){
arrayTemp.push(array[i])
}
/*当它等于的时候放哪，这里我想选择放到队列的前面，也就是从unshift后的第一个位置放置*/
if(array[i]===random){
arrayTemp.splice(unshiftHead,0,array[i])
}
}
/*将对应项覆盖原来的记录*/
for(var j = head , u=0j <= tailj++,u++){
array.splice(j,1,arrayTemp[u])
}
/*寻找中间项所在的index*/
var nowIndex = array.indexOf(random)
/*设置出口，当要放进去的片段只有2项的时候就可以收工了*/
if(arrayTemp.length <= 2){
return
}
/*递归，同时应用其左右两个区域*/
fastSort(array,head,nowIndex)
fastSort(array,nowIndex+1,tail)
}
JavaScript实现多维数组、对象数组排序，其实用的就是原生的sort()方法，用于对数组的元素进行排序。
sort() 方法用于对数组的元素进行排序。语法如下：
arrayObject.sort(sortby)例如：
function NumAscSort(a,b)
{
return a - b
}
function NumDescSort(a,b)
{
return b - a
}
var arr = new Array( 3600, 5010, 10100, 801)
arr.sort(NumDescSort)
alert(arr)
arr.sort(NumAscSort)
alert(arr)
算法的平均时间复杂度为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)
