JS实现随机化快速排序的实例代码_javascript技巧-js教程-PHP中文网

JS实现随机化快速排序的实例代码_javascript技巧

php中文网

发布： 2016-05-16 17:27:19

原创

1172人浏览过

算法的平均时间复杂度为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之间的数。

华锐行业电子商务系统

华锐行业电子商务系统2.0采用微软最新的.net3.5（c#）+mssql架构，代码进行全面重整及优化，清除冗余及垃圾代码，运行速度更快、郊率更高。全站生成静态、会员二级域名、竞价排名、企业会员有多套模板可供选择；在界面方面采用DIV+CSS进行设计，实现程序和界面分离，方便修改适合自己的个性界面，在用户体验方面，大量使用ajax技术，更加易用。程序特点:一、采用微软最新.net3.5+MSSQL

查看详情

复制代码代码如下:

　　
/****************************************
　　算法：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 　　if(array[j] 　　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 　　/******随机化拆分元素的主元*******/
　　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);