Javascript排序算法的介绍

2019-10-29 16:00:43来源：爱站网阅读 ()

关于JS的排序算法我们可以在网上搜到一堆，但是关于js的版本就非常零散，那么现在小编就为大家分享Javascript排序算法的介绍，感兴趣的我也没可以一起来看看吧。

具体代码及比较如下所示：

<!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;

}