算法的平均时间复杂度为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);
标签:
JS,随机化,排序

免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
狼山资源网 Copyright www.pvsay.com

评论“JS实现随机化快速排序的实例代码”

暂无“JS实现随机化快速排序的实例代码”评论...

RTX 5090要首发 性能要翻倍!三星展示GDDR7显存

三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。

首次推出的GDDR7内存模块密度为16GB,每个模块容量为2GB。其速度预设为32 Gbps(PAM3),但也可以降至28 Gbps,以提高产量和初始阶段的整体性能和成本效益。

据三星表示,GDDR7内存的能效将提高20%,同时工作电压仅为1.1V,低于标准的1.2V。通过采用更新的封装材料和优化的电路设计,使得在高速运行时的发热量降低,GDDR7的热阻比GDDR6降低了70%。