Common sorting algorithms in Javascript_javascript tips-JS Tutorial-php.cn

Common sorting algorithms in Javascript_javascript tips

WBOY

Release： 2016-05-16 19:16:04

Original

944 people have browsed it

The specific code and comparison are as follows:

Copy code The code is as follows:

Common sorting algorithms JavaScript version

随机数个数
最大随机数
重新生成
耗时(毫秒)：
冒泡排序
选择排序
插入排序
谢尔排序
快速排序(递归)
快速排序(堆栈)
归并排序
堆排序

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

个人理解

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

算法源码

复制代码代码如下:

 
// ---------- Some sorting algorithms 
// js uses sort to sort 
systemSort:function(array){ 
return array.sort(function (a, b){ 
return a - b; 
}); 
}, 
// Bubble sort
bubbleSort:function(array){ 
var i = 0 , len = array.length, 
j, d; 
for(; ifor(j=0; jif(array[ i] < array[j]){ 
d = array[j]; 
array[j] = array[i]; 
array[i] = d; 
} 
 } 
} 
return array; 
}, 
//Quick Sort
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){ 
//End condition
if(i == j ){ return }; 
var key = array [i]; 
var stepi = i; // Recording start position 
var stepj = j; // Recording end position 
while(j > i){ 
// j << ;-------------- Search forward
if(array[j] >= key){ 
j--; 
}else{ 
array [i] = array[j] 
//i ------------>>Look backwards
while(j > i){ 
if(array [i] > key){ 
array[j] = array[i]; 
break; 
} 
} 
} 
} 
// If first The extracted key is the smallest number 
if(stepi == i){ 
Sort( i, stepj); 
return ; 
} 
// The last space is reserved for key 
array[i] = key; 
// Recursion
Sort(stepi, i); 
Sort(j, stepj); 
} 
Sort(i, j); 
return array; 
}, 
// Insertion sort 
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; 
}, 
//Hill sort
//Jun.array .shellSort(Jun.array.df(10000)); 
shellSort:function(array){ 
// http://zh.wikipedia.org/zh/Hill sorting
// 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() See this optimal step size smaller array on the wiki
//var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481 , 90358, 19001, 4025, 836, 182, 34, 9, 1]//Step selection for large arrays 
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]); 
} 
// Sort by one step 
function stepSort(step){ 
//console.log(step) used Step statistics 
var i = 0, j = 0, f, tem, key; 
var stepLen = len%step > 0 ? parseInt(len/step) 1 : len/step; 

for(;i < step; i ){//Loop through the columns in sequence
for(j=1;/*j < stepLen && */step * j i < len; j ){//Loop through the columns in sequence Each row of each column
tem = f = step * j i; 
key = array[f]; 
while((tem-=step) >= 0){// Search upwards in sequence
if(array[tem] > key){ 
array[tem step] = array[tem]; 
}else{ 
break; 
} 
} 
array[ tem step ] = key; 
} 
} 
} 
return array; 
} 

Test code package download