富贵资源网

Javascript中的常见排序算法
站长资源 2024/11/18 佚名
37 1538
富贵资源网 Design By www.hznty.com
具体代码及比较如下所示：
复制代码 代码如下:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 
<html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312"> 
<head> 
<title> 常见排序算法 之 JavaScript版 </title> 
<meta http-equiv="content-type" content="text/html; charset=gb2312" /> 
<meta name="keywords" content="排序,算法,JavaScript排序" /> 
<meta name="description" content="用JavaScript实现的常见排序算法:冒泡排序,选择排序,插入排序,谢尔排序,快速排序(递归),快速排序(堆栈),归并排序,堆排序" /> 
<script type="text/javascript"> 
 Array.prototype.swap = function(i, j) 
 { 
 var temp = this[i]; 
 this[i] = this[j]; 
 this[j] = temp; 
 } 
 Array.prototype.bubbleSort = function() 
 { 
 for (var i = this.length - 1; i > 0; --i) 
 { 
 for (var j = 0; j < i; ++j) 
 { 
 if (this[j] > this[j + 1]) this.swap(j, j + 1); 
 } 
 } 
 } 
 Array.prototype.selectionSort = function() 
 { 
 for (var i = 0; i < this.length; ++i) 
 { 
 var index = i; 
 for (var j = i + 1; j < this.length; ++j) 
 { 
 if (this[j] < this[index]) index = j; 
 } 
 this.swap(i, index); 
 } 
 } 
 Array.prototype.insertionSort = function() 
 { 
 for (var i = 1; i < this.length; ++i) 
 { 
 var j = i, value = this[i]; 
 while (j > 0 && this[j - 1] > value) 
 { 
 this[j] = this[j - 1]; 
 --j; 
 } 
 this[j] = value; 
 } 
 } 
 Array.prototype.shellSort = function() 
 { 
 for (var step = this.length  1; step > 0; step = 1) 
 { 
 for (var i = 0; i < step; ++i) 
 { 
 for (var j = i + step; j < this.length; j += step) 
 { 
 var k = j, value = this[j]; 
 while (k >= step && this[k - step] > value) 
 { 
 this[k] = this[k - step]; 
 k -= step; 
 } 
 this[k] = value; 
 } 
 } 
 } 
 } 
 Array.prototype.quickSort = function(s, e) 
 { 
 if (s == null) s = 0; 
 if (e == null) e = this.length - 1; 
 if (s >= e) return; 
 this.swap((s + e)  1, e); 
 var index = s - 1; 
 for (var i = s; i <= e; ++i) 
 { 
 if (this[i] <= this[e]) this.swap(i, ++index); 
 } 
 this.quickSort(s, index - 1); 
 this.quickSort(index + 1, e); 
 } 
 Array.prototype.stackQuickSort = function() 
 { 
 var stack = [0, this.length - 1]; 
 while (stack.length > 0) 
 { 
 var e = stack.pop(), s = stack.pop(); 
 if (s >= e) continue; 
 this.swap((s + e)  1, e); 
 var index = s - 1; 
 for (var i = s; i <= e; ++i) 
 { 
 if (this[i] <= this[e]) this.swap(i, ++index); 
 } 
 stack.push(s, index - 1, index + 1, e); 
 } 
 } 
 Array.prototype.mergeSort = function(s, e, b) 
 { 
 if (s == null) s = 0; 
 if (e == null) e = this.length - 1; 
 if (b == null) b = new Array(this.length); 
 if (s >= e) return; 
 var m = (s + e)  1; 
 this.mergeSort(s, m, b); 
 this.mergeSort(m + 1, e, b); 
 for (var i = s, j = s, k = m + 1; i <= e; ++i) 
 { 
 b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++]; 
 } 
 for (var i = s; i <= e; ++i) this[i] = b[i]; 
 } 
 Array.prototype.heapSort = function() 
 { 
 for (var i = 1; i < this.length; ++i) 
 { 
 for (var j = i, k = (j - 1)  1; k >= 0; j = k, k = (k - 1)  1) 
 { 
 if (this[k] >= this[j]) break; 
 this.swap(j, k); 
 } 
 } 
 for (var i = this.length - 1; i > 0; --i) 
 { 
 this.swap(0, i); 
 for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1) 
 { 
 if (k == i || this[k] < this[k - 1]) --k; 
 if (this[k] <= this[j]) break; 
 this.swap(j, k); 
 } 
 } 
 } 
 function generate() 
 { 
 var max = parseInt(txtMax.value), count = parseInt(txtCount.value); 
 if (isNaN(max) || isNaN(count)) 
 { 
 alert("个数和最大值必须是一个整数"); 
 return; 
 } 
 var array = []; 
 for (var i = 0; i < count; ++i) array.push(Math.round(Math.random() * max)); 
 txtInput.value = array.join("\n"); 
 txtOutput.value = ""; 
 } 
 function demo(type) 
 { 
 var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n"); 
 for (var i = 0; i < array.length; ++i) array[i] = parseInt(array[i]); 
 var t1 = new Date(); 
 eval("array." + type + "Sort()"); 
 var t2 = new Date(); 
 lblTime.innerText = t2.valueOf() - t1.valueOf(); 
 txtOutput.value = array.join("\n"); 
 } 
</script> 
</head> 
<body onload="generate();"> 
<table style="font-size:12px;"> 
<tr> 
 <td align="right"> 
 <textarea id="txtInput" style="width:120px;height:500px;" readonly></textarea> 
 </td> 
 <td width="150" align="center"> 
 随机数个数<input id="txtCount" value="500" style="width:50px" /><br /><br /> 
 最大随机数<input id="txtMax" value="1000" style="width:50px" /><br /><br /> 
 <button onclick="generate()">重新生成</button><br /><br /><br /><br /> 
 耗时(毫秒)：<label id="lblTime"></label><br /><br /><br /><br /> 
 <button onclick="demo('bubble');">冒泡排序</button><br /><br /> 
 <button onclick="demo('selection');">选择排序</button><br /><br /> 
 <button onclick="demo('insertion');">插入排序</button><br /><br /> 
 <button onclick="demo('shell');">谢尔排序</button><br /><br /> 
 <button onclick="demo('quick');">快速排序(递归)</button><br /><br /> 
 <button onclick="demo('stackQuick');">快速排序(堆栈)</button><br /><br /> 
 <button onclick="demo('merge');">归并排序</button><br /><br /> 
 <button onclick="demo('heap');">堆排序</button><br /><br /> 
 </td> 
 <td align="left"> 
 <textarea id="txtOutput" style="width:120px;height:500px;" readonly></textarea> 
 </td> 
</tr> 
</table> 
</body> 
</html> 

快速排序, 插入排序, 希尔排序, 冒泡排序, quickSort, insertSort, shellSort, bubbleSort, javascript排序
说明
写这个主要是为了锻炼自己，并无实际意义。
每个浏览器测试得出的数据会不一样。比如我用chrome 测试 一般快速排序都会最快，IE 则根据数组长度有可能希尔最快。
不要用太大数据去测试冒泡排序(浏览器崩溃了我不管)
如果有兴趣可以 下载测试页面

个人理解

冒泡排序：最简单，也最慢，貌似长度小于7最优
插入排序： 比冒泡快，比快速排序和希尔排序慢，较小数据有优势
快速排序：这是一个非常快的排序方式，V8的sort方法就使用快速排序和插入排序的结合
希尔排序：在非chrome下数组长度小于1000，希尔排序比快速更快
系统方法：在forfox下系统的这个方法非常快

算法源码
复制代码 代码如下:
// ---------- 一些排序算法
// js 利用sort进行排序
systemSort:function(array){
return array.sort(function(a, b){
return a - b;
});
},
// 冒泡排序
bubbleSort:function(array){
var i = 0, len = array.length,
j, d;
for(; i<len; i++){
for(j=0; j<len; j++){
if(array[i] < array[j]){
d = array[j];
array[j] = array[i];
array[i] = d;
}
}
}
return array;
},
// 快速排序
quickSort:function(array){
//var array = [8,4,6,2,7,9,3,5,74,5];
//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];
var i = 0;
var j = array.length - 1;
var Sort = function(i, j){
// 结束条件
if(i == j ){ return };
var key = array[i];
var stepi = i; // 记录开始位置
var stepj = j; // 记录结束位置
while(j > i){
// j <<-------------- 向前查找
if(array[j] >= key){
j--;
}else{
array[i] = array[j]
//i++ ------------向后查找
while(j > ++i){
if(array[i] > key){
array[j] = array[i];
break;
}
}
}
}
// 如果第一个取出的 key 是最小的数
if(stepi == i){
Sort(++i, stepj);
return ;
}
// 最后一个空位留给 key
array[i] = key;
// 递归
Sort(stepi, i);
Sort(j, stepj);
}
Sort(i, j);
return array;
},
// 插入排序
insertSort:function(array){
// http://baike.baidu.com/image/d57e99942da24e5dd21b7080
// http://baike.baidu.com/view/396887.htm
//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];
var i = 1, j, step, key,
len = array.length;
for(; i < len; i++){
step = j = i;
key = array[j];
while(--j > -1){
if(array[j] > key){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = key;
}
return array;
},
// 希尔排序
//Jun.array.shellSort(Jun.array.df(10000));
shellSort:function(array){
// http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
// var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];
var stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在维基上看到这个最优的步长 较小数组
//var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//针对大数组的步长选择
var i = 0;
var stepArrLength = stepArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i < stepArrLength; i++){
if(stepArr[i] > len2){
continue;
}
stepSort(stepArr[i]);
}
// 排序一个步长
function stepSort(step){
//console.log(step) 使用的步长统计
var i = 0, j = 0, f, tem, key;
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step;

for(;i < step; i++){// 依次循环列
for(j=1;/*j < stepLen && */step * j + i < len; j++){//依次循环每列的每行
tem = f = step * j + i;
key = array[f];
while((tem-=step) >= 0){// 依次向上查找
if(array[tem] > key){
array[tem+step] = array[tem];
}else{
break;
}
}
array[tem + step ] = key;
}
}
}
return array;
}

测试代码打包下载
富贵资源网 Design By www.hznty.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
富贵资源网 Design By www.hznty.com
www.hznty.com 富贵资源网
20,135影音资源
44,641技术资源
2,817软件资源
435,032站长资源

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接
富贵资源网 Design By www.hznty.com