Home >Web Front-end >JS Tutorial >How to implement various sorting methods using js
How to implement various sorting methods using js
- 亚连Original
- 2018-06-13 17:48:581492browse
Below I will share with you an article (detailed explanation) on the differences between various sorting methods and sort methods based on js. It has a good reference value and I hope it will be helpful to everyone.
I had a whim today and wanted to know whether the sort method has advantages over various sortings, so I made a test by referring to other people's codes. The results were surprising. Here is the code.
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width,initial-scale=1.0,maximum-scale=1.0,user-scalable=0">
<title>图片列表生成交互组件</title>
<style>
* {
margin: 0;
border: 0;
}
html, body {
height: 100%;
}
#p {
height: 100%;
width: 100%;
}
</style>
</head>
<body>
<p id="p"></p>
<script src="myNeedExtend.js"></script>
<script>
// ---------- 一些排序算法
Sort = {
// 利用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 tempi = i; // 记录开始位置
var tempj = 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(tempi == i){
Sort(++i, tempj);
return ;
}
// 最后一个空位留给 key
array[i] = key;
// 递归
Sort(tempi, i);
Sort(j, tempj);
}
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, temp, key, len = array.length;
for(; i < len; i++){
temp = 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;
},
// 希尔排序
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 tempArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1];
// reverse() 在维基上看到这个最优的步长 较小数组
var tempArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1];
//针对大数组的步长选择
var i = 0;
var tempArrLength = tempArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i < tempArrLength; i++){
if(tempArr[i] > len2){
continue;
}
tempSort(tempArr[i]);
}
// 排序一个步长
function tempSort(temp){
//console.log(temp) 使用的步长统计
var i = 0, j = 0, f, tem, key;
var tempLen = len%temp > 0 ? parseInt(len/temp) + 1 : len/temp;
for(;i < temp; i++){// 依次循环列
for(j=1;/*j < tempLen && */temp * j + i < len; j++){
//依次循环每列的每行
tem = f = temp * j + i;
key = array[f];
while((tem-=temp) >= 0){
// 依次向上查找
if(array[tem] > key){
array[tem+temp] = array[tem];
}else{
break;
}
}
array[tem + temp ] = key;
}
}
}
return array;
}
};
testArrs = [];
for (var i = 10000000; i > 0; i--) {
testArrs.push(i);
}
function test(fun,arr) {
console.log(arr);
var oldTime = +new Date();
var new_arr = Sort[fun](arr);
var newTime = +new Date();
console.log(new_arr);
console.log(newTime-oldTime);
}
/*
* sort排序 systemSort
* 冒泡排序 bubbleSort
* 快速排序 quickSort
* 插入排序 insertSort
* 希尔排序 shellSort
*
* */
test("systemSort",testArrs);
</script>
</body>
</html>The above method passes the test time, and then analyzes which sorting method saves time. Time is life. Using the correct method can save a lot of time, especially when big data is running.
First look at the time it takes to process an array of 10,000 lengths:
* sort sorting systemSort 11
* Bubble sort bubbleSort 169
* quick sort quickSort 144
* insertion sort insertSort 139
* Hill sort shellSort 3
Test 100,000-long array data:
* sort sorting systemSort 63
* Bubble sorting bubbleSort 16268
* Quick sorting quickSort reports an error directly
* Insertion sorting insertSort 13026
* Hill sorting shellSort 8
Test an array with a length of one million:
* sort sort systemSort 575
* Bubble sort bubbleSort time unknown
* Quick sort quickSort reports an error directly
* Insertion sort insertSort crashes directly
* Hill sort shellSort 93
Test an array of 10 million long:
* sort sorting systemSort 7039
* Bubble sort bubbleSort not tested
* quick sort quickSort not tested
* insertion sort insertSort not tested
* Hill sorting shellSort 1225
Testing an array of 100 million long:
* sort systemSort crashes directly
* Bubble sort bubbleSort not tested
* Fast Sort quickSort Not tested
* Insertion sort insertSort Not tested
* Hill sort shellSort 19864
Finally passed the test,In the worst case , I found that Hill sorting is still the best, and it is even faster than the system sorting. It is really surprising. In this way, everyone can see what method needs to be used for sorting under what circumstances.
Then We test under random conditions:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width,initial-scale=1.0,maximum-scale=1.0,user-scalable=0">
<title>图片列表生成交互组件</title>
<style>
* {
margin: 0;
border: 0;
}
html, body {
height: 100%;
}
#p {
height: 100%;
width: 100%;
}
</style>
</head>
<body>
<p id="p"></p>
<script src="myNeedExtend.js"></script>
<script>
// ---------- 一些排序算法
Sort = {
// 利用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 tempi = i; // 记录开始位置
var tempj = 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(tempi == i){
Sort(++i, tempj);
return ;
}
// 最后一个空位留给 key
array[i] = key;
// 递归
Sort(tempi, i);
Sort(j, tempj);
}
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, temp, key, len = array.length;
for(; i < len; i++){
temp = 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;
},
// 希尔排序
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 tempArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1];
// reverse() 在维基上看到这个最优的步长 较小数组
var tempArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1];
//针对大数组的步长选择
var i = 0;
var tempArrLength = tempArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i < tempArrLength; i++){
if(tempArr[i] > len2){
continue;
}
tempSort(tempArr[i]);
}
// 排序一个步长
function tempSort(temp){
//console.log(temp) 使用的步长统计
var i = 0, j = 0, f, tem, key;
var tempLen = len%temp > 0 ? parseInt(len/temp) + 1 : len/temp;
for(;i < temp; i++){// 依次循环列
for(j=1;/*j < tempLen && */temp * j + i < len; j++){
//依次循环每列的每行
tem = f = temp * j + i;
key = array[f];
while((tem-=temp) >= 0){
// 依次向上查找
if(array[tem] > key){
array[tem+temp] = array[tem];
}else{
break;
}
}
array[tem + temp ] = key;
}
}
}
return array;
}
};
testArrs = [];
for (var i = 0; i < 10000000; i++) {
testArrs.push(Math.random());
}
function test(fun,arr) {
var oldTime = +new Date();
var new_arr = Sort[fun](arr);
var newTime = +new Date();
console.log(fun);
console.log(newTime-oldTime);
}
/*
* sort排序 systemSort
* 冒泡排序 bubbleSort
* 快速排序 quickSort
* 插入排序 insertSort
* 希尔排序 shellSort
*
* */
test("systemSort",testArrs);
//test("bubbleSort",testArrs);
//test("quickSort",testArrs);
test("insertSort",testArrs);
test("shellSort",testArrs);
</script>
</body>
</html>Test a 10 million-long array:
* sort sorting systemSort 8842
* Bubble sort bubbleSort not tested
* Quick sort quickSort not tested
* Insertion sort insertSort 45
* Hill sort shellSort 1133
In unknown situations Under better circumstances, insertion sort is the most efficient
The above is what I compiled for everyone. I hope it will be helpful to everyone in the future.
Related articles:
Detailed explanation of the separation and combination of vue-admin and backend (flask)
Detailed explanation of the basics in Vue webpack Configuration
Explain the basic configuration in detail in Vue webpack
How to build a multi-person chat room in the nodejs express environment
The above is the detailed content of How to implement various sorting methods using js. For more information, please follow other related articles on the PHP Chinese website!
Related articles
See more- An in-depth analysis of the Bootstrap list group component
- Detailed explanation of JavaScript function currying
- Complete example of JS password generation and strength detection (with demo source code download)
- Angularjs integrates WeChat UI (weui)
- How to quickly switch between Traditional Chinese and Simplified Chinese with JavaScript and the trick for websites to support switching between Simplified and Traditional Chinese_javascript skills