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);