Summary of several common sorting algorithms in JavaScript

Summary of several common sorting algorithms in JavaScript_javascript skills

WBOY

Release： 2016-05-16 18:10:34

Original

911 people have browsed it

Explanation
Writing this is mainly to train myself and has no practical significance.
The data obtained from each browser test will be different. For example, I used chrome to test and generally quick sort is the fastest, while in IE, Hill may be the fastest depending on the array length.
Don’t use too much data to test bubble sorting (I don’t care if the browser crashes)
If you are interested, you can download the test page

Personal understanding

Bubble sort: the simplest and slowest, seems to be optimal if the length is less than 7
Insertion sort: faster than bubble, slower than quick sort and Hill sort, smaller data has advantages
Quick sort: This is a very fast sorting method. V8's sort method uses a combination of quick sort and insertion sort
Hill sort: When the array length is less than 1000 under non-chrome, Hill sort is faster than quick
System method: This method of the system under forfox is very fast

Algorithm source code

Copy code The code is as follows:

 
// ---------- Some sorting algorithms
// js uses sort for sorting
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 the first key taken out is the smallest number 
if(stepi == i){ 
Sort( i, stepj); 
return ; 
} 
// The last space is reserved for key 
array[i] = key; 
// Recursive 
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; 
}, 
// Hope Sorting 
//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 stepArrLeng th = 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) step statistics used 
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 
for(j=1;/*j < stepLen && */step * j i < ; len; j ){//Loop through each row of each column in turn 
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