JS实现随机化快速排序的实例代码
2023-06-13 09:15:03 时间
算法的平均时间复杂度为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;
****************************************/
functionsplit(array,low,high){
vari=low;
varx=array[low];
for(varj=low+1;j<=high;j++){
if(array[j]<=x){
i++;
if(i!=j){
vartemp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
temp=array[low];
array[low]=array[i];
array[i]=temp;
returni;
}
/****************************************
算法:rquicksort
输入:A[0...n-1]
输出:按非降序排列数组A[0...n-1]
rquicksort(A,0,n-1);
****************************************/
functionrquicksort(array,low,high){
if(low<high){
/******随机化拆分元素的主元*******/
varv=parseInt(Math.random()*(high-low+1)+low);
vartmp=array[low];
array[low]=array[v];
array[v]=tmp;
/******随机化拆分元素的主元*******/
varw=split(array,low,high);
rquicksort(array,low,w-1);
rquicksort(array,w+1,high);
returnarray;
}
}
vararray=[33,22,11,88,23,32];
array=rquicksort(array,0,array.length-1);
console.log(array);
相关文章
- fullPage.js全屏滚动插件
- Js排序算法_js 排序算法
- js中倒计时_js倒计时特效
- touch.js的使用总结
- 【JS 逆向百例】猿人学系列 web 比赛第二题:js 混淆 - 动态 cookie,详细剖析
- 对滚动条添加JS事件详解编程语言
- 使用JS连接MySQL数据库:实现化繁为简(js连接mysql数据库)
- JS技术连接Oracle数据库实现数据交互(js连接oracle实例)
- 使用JS操作Oracle数据库探索潜在可能性(js和oracle数据库)
- JS在Oracle中的应用(js如何oracle)
- Redis和JavaScript的结合实现了何种不可思议的奇迹(redis能在js连接吗)
- textbox在光标位置插入字符功能的js实现(兼容ie,firefox)
- js截取函数(indexOf,join等)
- Js网页另存为实现代码
- Json字符串转换为JS对象的高效方法实例
- JS实现的省份级联实例代码
- js点击更换背景颜色或图片的实例代码
- js判断选择时间不能小于当前时间的示例代码
- JS截取字符串常用方法详细整理
- js操作label给label赋值及取label的值示例
- JS获取键盘上任意按键的值(实例代码)
- js去掉空格实例Trim()LTrim()RTrim()
- JS操作Array数组的方法及属性实例解析
- 使用Node.js实现一个简单的FastCGI服务器实例
- js调试系列断点与动态调试[基础篇]
- node.js中的fs.write方法使用说明
- js正则查找match()与替换replace()用法实例