http://www.nowamagic.net/javascript/js_SortEffectiveInJavascript.php
JavaScript排序性能比较
2011-02-15
排序是经常使用的编程例子,在JavaScript里各种排序的性能又如何呢?每个浏览器测试得出的数据会不一样。比如我用chrome 测试 一般快速排序都会最快,IE 则根据数组长度有可能希尔最快。
不要用太大数据去测试冒泡排序(浏览器崩溃了我不管)。
[quickSort]: 0,1,2,3,4,5,6,7,8,9
[insertSort]: 0,1,2,3,4,5,6,7,8,9
[shellSort]: 0,1,2,3,4,5,6,7,8,9
[systemSort]: 0,1,2,3,4,5,6,7,8,9
[bubbleSort]: 0,1,2,3,4,5,6,7,8,9
快速排序 插入排序 希尔排序 系统方法 冒泡排序 清空
测试数组长度:
测试次数:10次
数组太长请慎用 冒泡排序
测试次数:10次
数组太长请慎用 冒泡排序
快速排序 | 1000 | 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, | 0.3 | 测试 |
插入排序 | 1000 | 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, | 1.3 | 测试 |
希尔排序 | 1000 | 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, | 0.4 | 测试 |
系统方法 | 1000 | 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, | 0.2 | 测试 |
冒泡排序 | 1000 | 6, 5, 5, 5, 3, 4, 5, 5, 5, 5, | 4.8 | 小心测试 |
个人理解:
- 冒泡排序:最简单,也最慢,貌似长度小于7最优
- 插入排序: 比冒泡快,比快速排序和希尔排序慢,较小数据有优势
- 快速排序:这是一个非常快的排序方式,V8的sort方法就使用快速排序和插入排序的结合
- 希尔排序:在非chrome下数组长度小于1000,希尔排序比快速更快
- 系统方法:在forfox下系统的这个方法非常快
JavaScript Code
001 |
<script type= "text/javascript" >
|
002 |
Jun = {}; |
003 |
Jun.array = { |
004 |
|
005 |
|
006 |
df: function (len){
|
007 |
var array = [], i;
|
008 |
len = len || 1000;
|
009 |
for (i = 0; i< len; i++){
|
010 |
array.push(i);
|
011 |
}
|
012 |
return array.sort( function (){ return Math.random() > 0.5});
|
013 |
},
|
014 |
// Jun.array.test();
|
015 |
test: function (method, arrayLength, callBack){
|
016 |
|
017 |
var times = [];
|
018 |
var i = 0;
|
019 |
var sum = 0;
|
020 |
var len = 10;
|
021 |
|
022 |
for (;i<len;i++){
|
023 |
test();
|
024 |
}
|
025 |
|
026 |
for (i=0;i<times.length;i++){
|
027 |
sum+=times[i];
|
028 |
}
|
029 |
|
030 |
|
031 |
032 |
function test(){
|
033 |
var array = Jun.array.df(arrayLength);
|
034 |
var st = new Date().getTime();
|
035 |
Jun.array[method](array); //shellSort quickSort systemSort
|
036 |
var d = new Date().getTime() - st;
|
037 |
callBack && callBack( new Date().getTime() - st);
|
038 |
times.push(d);
|
039 |
}
|
040 |
|
041 |
return sum / len;
|
042 |
},
|
043 |
|
044 |
// ---------- 一些排序算法
|
045 |
// js 利用sort进行排序
|
046 |
systemSort: function (array){
|
047 |
return array.sort( function (a, b){
|
048 |
return a - b;
|
049 |
});
|
050 |
},
|
051 |
// 冒泡排序
|
052 |
bubbleSort: function (array){
|
053 |
var i = 0, len = array.length,
|
054 |
j, d;
|
055 |
for (; i<len; i++){
|
056 |
for (j=0; j<len; j++){
|
057 |
if (array[i] < array[j]){
|
058 |
d = array[j];
|
059 |
array[j] = array[i];
|
060 |
array[i] = d;
|
061 |
}
|
062 |
}
|
063 |
}
|
064 |
return array;
|
065 |
},
|
066 |
// 快速排序
|
067 |
quickSort: function (array){
|
068 |
//var array = [8,4,6,2,7,9,3,5,74,5];
|
069 |
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
|
070 |
var i = 0;
|
071 |
var j = array.length - 1;
|
072 |
var Sort = function (i, j){
|
073 |
|
074 |
// 结束条件
|
075 |
if (i == j ){ return };
|
076 |
|
077 |
var key = array[i];
|
078 |
var stepi = i; // 记录开始位置
|
079 |
var stepj = j; // 记录结束位置
|
080 |
|
081 |
while (j > i){
|
082 |
// j <<-------------- 向前查找
|
083 |
if (array[j] >= key){
|
084 |
j--;
|
085 |
} else {
|
086 |
array[i] = array[j]
|
087 |
//i++ ------------>>向后查找
|
088 |
while (j > ++i){
|
089 |
if (array[i] > key){
|
090 |
array[j] = array[i];
|
091 |
break ;
|
092 |
}
|
093 |
}
|
094 |
}
|
095 |
}
|
096 |
|
097 |
// 如果第一个取出的 key 是最小的数
|
098 |
if (stepi == i){
|
099 |
Sort(++i, stepj);
|
100 |
return ;
|
101 |
}
|
102 |
|
103 |
// 最后一个空位留给 key
|
104 |
array[i] = key;
|
105 |
|
106 |
// 递归
|
107 |
Sort(stepi, i);
|
108 |
Sort(j, stepj);
|
109 |
}
|
110 |
|
111 |
Sort(i, j);
|
112 |
|
113 |
return array;
|
114 |
},
|
115 |
|
116 |
// 插入排序
|
117 |
insertSort: function (array){
|
118 |
|
121 |
//var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
|
122 |
|
123 |
var i = 1, j, step, key,
|
124 |
len = array.length;
|
125 |
|
126 |
for (; i < len; i++){
|
127 |
|
128 |
step = j = i;
|
129 |
key = array[j];
|
130 |
|
131 |
while (--j > -1){
|
132 |
if (array[j] > key){
|
133 |
array[j+1] = array[j];
|
134 |
} else {
|
135 |
break ;
|
136 |
}
|
137 |
}
|
138 |
|
139 |
array[j+1] = key;
|
140 |
}
|
141 |
|
142 |
return array;
|
143 |
},
|
144 |
|
145 |
// 希尔排序
|
146 |
//Jun.array.shellSort(Jun.array.df(10000));
|
147 |
shellSort: function (array){
|
148 |
150 |
// var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];
|
151 |
|
152 |
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在维基上看到这个最优的步长 较小数组
|
153 |
//var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//针对大数组的步长选择
|
154 |
var i = 0;
|
155 |
var stepArrLength = stepArr.length;
|
156 |
var len = array.length;
|
157 |
var len2 = parseInt(len/2);
|
158 |
|
159 |
for (;i < stepArrLength; i++){
|
160 |
if (stepArr[i] > len2){
|
161 |
continue ;
|
162 |
}
|
163 |
|
164 |
stepSort(stepArr[i]);
|
165 |
}
|
166 |
167 |
// 排序一个步长
|
168 |
function stepSort(step){
|
169 |
|
170 |
//console.log(step) 使用的步长统计
|
171 |
|
172 |
var i = 0, j = 0, f, tem, key;
|
173 |
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step;
|
174 |
|
175 |
|
176 |
for (;i < step; i++){ // 依次循环列
|
177 |
178 |
for (j=1; /*j < stepLen && */ step * j + i < len; j++){ //依次循环每列的每行
|
179 |
tem = f = step * j + i;
|
180 |
key = array[f];
|
181 |
182 |
while ((tem-=step) >= 0){ // 依次向上查找
|
183 |
if (array[tem] > key){
|
184 |
array[tem+step] = array[tem];
|
185 |
} else {
|
186 |
break ;
|
187 |
}
|
188 |
}
|
189 |
|
190 |
array[tem + step ] = key;
|
191 |
|
192 |
}
|
193 |
}
|
194 |
|
195 |
}
|
196 |
|
197 |
return array;
|
198 |
|
199 |
}
|
200 |
};
|
201 |
</script> |
202 |
203 |
<script type= "text/javascript" >
|
204 |
var jelle = {
|
205 |
index:1,
|
206 |
$: function (id){
|
207 |
return document.getElementById(id);
|
208 |
},
|
209 |
test: function (method, num){
|
210 |
var arrayLength = parseInt(jelle.$( 'arrayLength' ).value);
|
211 |
jelle.index = num;
|
212 |
jelle.$( 'length_' +num).innerHTML = arrayLength;
|
213 |
jelle.$( 'times_' +num).innerHTML = '' ;
|
214 |
jelle.$( 'time_' +num).innerHTML = Jun.array.test(method, arrayLength, jelle.insert);;
|
215 |
},
|
216 |
insert: function (num){
|
217 |
jelle.$( 'times_' +jelle.index).innerHTML += num+ ', ' ;
|
218 |
},
|
219 |
correctness: function (method){
|
220 |
var array = new Function( 'return ' + jelle.$( 'testArray' ).value)();
|
221 |
jelle.$( 'testResults' ).innerHTML += '<div>[' +method+ ']: ' +Jun.array[method](array)+ '</div>' ;
|
222 |
}
|
223 |
}
|
224 |
</script> |
随机文章推荐 |
- JavaScript实现的颜色选择器
- JavaScript团队编程规范与建议
- PNG 透明兼容 IE6 的几种方法
- DOM 编程艺术:getElementsByTagName() 方法
- 动态增加元素的DOM操作
- JavaScript计算两个日期的时间差
- JavaScript 滚动文字
- 金额数字格式化与四舍五入
- Google 首页纪念牛顿特效
- 判断单选按钮与上传文件不能为空
- 你需要知道的JavaScript的背景知识
- JavaScript的事件冒泡是什么
<iframe id="aswift_1" style="left: 0px; position: absolute; top: 0px;" name="aswift_1" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" width="200" height="200"></iframe> |
网站分类 |
相关推荐
绝对是好东西 如果你刚好找这方面的资料要实现点击表头就产生排序,绝对实用,物超所值 轻量级JavaScript表格内容排序代码 对生产的html进行排序,不需要与数据库交互,速度性能好
直接插入排序 直接插入排序(Straight Insertion Sort)是一种...直接插入排序适用于待排序序列较小或基本有序的情况,因为它在处理小规模数据时效率较高,且在处理有序或基本有序的数据时性能优于其他一些排序算法。
JavaScript排序算法什么是算法? 算法是要执行的自包含的分步操作集。 算法执行计算,数据处理和/或自动推理任务。 “优雅”(紧凑)程序,“好”(快速)程序:“简单和优雅”的概念非正式出现在Knuth,恰恰出现在...
查询包括过滤、下钻、合成、排序和/或聚合的一个或多个步骤。 它还可选地允许您生成动态结果,这样如果原始 Array 中的任何内容发生更改,查询结果将立即反映这些更改。 它不做什么? 其他一切。 当前状态 语法现...
一、希尔排序(性能最好) 如果要从大到小排列,则 while(arr[n] > arr[n – interval] && n > 0) 。 // 希尔排序算法 function xier(arr){ var interval = parseInt(arr.length / 2);//分组间隔设置 while...
相反,在以下情况下,它可以极大地提高您的性能: 排序是您的瓶颈,并且 数组中的元素需要昂贵的预处理才能确定其正确顺序。 概念 想象一下,我们正在对这个数字数组进行排序,以字符串表示: [ '12.4' , '1.62' ...
简单函数binaryInsert(array, value, comparator) ,可为javascript中的排序数组提供二进制插入功能。 这主要用于较大的阵列,可以在查看性能提升。 二进制插入为O(log(n))而Javascript的.sort() (使用quicksort或...
现在,您可以执行和比较不同JavaScript代码段的执行速度,还可以通过简单和简短的URL共享它并与其他人在线协作。 特征: 免费使用 在Suitecase中创建多个测试。 排序和调整大小测试 运行个别测试 “ Setup ...
它在生产模式下正确捆绑了React,并优化了构建以获得最佳性能。 最小化构建,文件名包含哈希。 您的应用已准备好进行部署! 有关更多信息,请参见有关的部分。npm run eject 注意:这是单向操作。 eject ,您将无法...
1.3条件比较字符串 1.4在字符串中查找子字符串 1.5从一个字符串提取子字符串 1.6检查一个存在的、非空的字符串 1.7将一个关键字字符串分解为单独的关键字 1.8插入特殊字符 1.9处理textarea的单个行 ...
支持状态持久化,包括持久化列宽,列隐藏,排序,列顺序状态 支持二层级的数据 支持金额和时间格式化 支持高亮行 支持多行复杂表头 支持排序列 支持重设宽高,重新加载数据 特色 兼容性好,兼容IE6-10,Firefox、...
冒泡排序可谓是最经典的排序算法了,它是基于比较的排序算法,时间复杂度为O(n^2),其优点是实现简单,n较小时性能较好。 1)算法原理 相邻的数据进行两两比较,小数放在前面,大数放在后面,这样一趟下来,最小...
性能javascript_algorithms Javascript 中各种算法的实现。 所有问题都有单元测试覆盖。 为什么是 JavaScript? 它是我目前最强大的语言,考虑到 V8 取得的令人印象深刻的进步,我认为 Javascript 拥有美好的未来。 ...
Javascript 高性能之递归,迭代,查表法详解 递归 概念:函数通过直接调用自身,或者两个函数之间的互相调用,来达到一定的目的,比如排序,阶乘等 简单的递归 阶乘 function factorial(n) { if (n == 0) { ...
多重 全面的数据结构和LINQ JavaScript库。 什么是多重 Multiplex是JavaScript中... HashSet不含重复元素的高性能值集。 SortedList按键排序的键/值对的集合。 LinkedList双链表。 Queue -对象的先进先出(FIFO)
在非英语语言中,使用String.compare()的Javascript Array.sort给出错误的顺序,例如在德语中,正确的排序顺序为:Arzt,Ärzte,Ast,Baum,Zeder,而Arzt,Ast,Baum,Zeder,Ärzte与英语相反/ ASCII字符串...
网络性能:Yarn 有效地将请求排序,避免请求堆积,以最大限度地提高网络利用率。多个注册表:无论从 npm 或 Bower 安装任何包,能保持包工作流程相同。网络恢复:单个请求失败不会导致安装失败。 请求在失败时会...
Java是一种高性能、跨平台的面向对象编程语言。它由Sun Microsystems(现在是Oracle Corporation)的James Gosling等人在1995年推出,被设计为一种简单、健壮、可移植、多线程、动态的语言。Java的主要特点和优势...
它提供出色的性能,没有第 3 方依赖项,并且可以与所有主要的 JavaScript 框架顺利集成。 以下是我们的网格在启用多个过滤器和分组的情况下的样子: 功能 除了您期望从任何网格中获得的标准功能集之外: 列交互...
它在生产模式下正确捆绑了React,并优化了构建以获得最佳性能。 最小化构建,文件名包含哈希。 您的应用已准备好进行部署! 有关更多信息,请参见有关的部分。yarn eject 注意:这是单向操作。 eject ,您将无法...