Heim >Web-Frontend >js-Tutorial >Detaillierte Erläuterung der Unterschiede zwischen verschiedenen js-Sortiermethoden und Sortiermethoden
Detaillierte Erläuterung der Unterschiede zwischen verschiedenen js-Sortiermethoden und Sortiermethoden
- 小云云Original
- 2018-01-05 17:55:231882Durchsuche
Ich hatte heute einen plötzlichen Gedanken und wollte wissen, ob die Sortiermethode Vorteile gegenüber verschiedenen Sortiermethoden hat. Dieser Artikel teilt Ihnen hauptsächlich einen Artikel über die Unterschiede zwischen verschiedenen Sortiermethoden und Sortiermethoden basierend auf js (ausführliche Erklärung). Hat einen guten Referenzwert. Ich hoffe, es hilft allen. Folgen wir dem Herausgeber und schauen wir uns das an. Ich hoffe, es kann allen helfen.
<!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>
Die obige Methode besteht die Testzeit und analysiert dann, welche Sortiermethode Zeit spart. Zeit ist Leben, und die Verwendung der richtigen Methode kann viel Zeit sparen, insbesondere bei der Ausführung großer Datenmengen.
Sehen Sie sich zunächst die Zeit an, die zum Verarbeiten eines Arrays mit 10.000 Längen benötigt wird:
* sort sorting systemSort 11
* bubble sort bubbleSort 169
* quick sort quickSort 144
* Insertion sort insertSort 139
* Hill sort shellSort 3
100.000 Array-Daten testen:
* sort sort systemSort 63
* Bubble sort bubbleSort 16268
* Quick Sort QuickSort meldet einen Fehler direkt
* Insertion Sort InsertSort 13026
* Hill Sort ShellSort 8
Testen Sie ein Array mit einer Million Länge:
* Sort Sort SystemSort 575
* Blasensortierung, BubbleSort-Zeit unbekannt
* Schnelle Sortierung, schnelle Sortierung, direkt einen Fehler melden
* Einfügungssortierung, insertSort-Absturz direkt
* Hill-Sortierung, ShellSort 93
Testen Sie ein 10 Millionen langes Array:
* Sort Sorting SystemSort 7039
* Bubble Sort BubbleSort nicht getestet
* Quick Sort QuickSort nicht getestet
* Insertion Sort InsertSort nicht getestet
* Hill Sort ShellSort 1225
Testen ein Array mit einer Länge von 100 Millionen:
* sort Sorting SystemSort ist direkt abgestürzt
* Bubble Sort BubbleSort nicht getestet
* Quick Sort QuickSort nicht getestet
* Insertion Sort InsertSort nicht getestet
* Hill-Sortierung ShellSort 19864
Im schlimmsten Fall wurde festgestellt, dass die Hill-Sortierung immer noch die beste ist, und das ist wirklich überraschend In welcher Situation muss welche Methode zum Sortieren verwendet werden, oder?
Dann testen wir es unter zufälligen Bedingungen:
<!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>
Testen Sie ein 10 Millionen langes Array:
* Sort Sorting SystemSort 8842
* Bubble Sort BubbleSort nicht getestet
* Quick Sort QuickSort nicht getestet
* Insertion Sort InsertSort 45
* Hill Sort ShellSort 1133
In unbekannten Situationen und In relativ guten Situationen ist die Einfügungssortierung am effizientesten
Verwandte Empfehlungen:
Zusammenfassung der PHP-Array-Sortiermethode
Ausführliche Erklärung der Verwendung von Sortiermethoden in JavaScript-Algorithmen
Einführung in PHP-Array-Funktionen und Zusammenfassung der Array-Sortiermethoden
Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Unterschiede zwischen verschiedenen js-Sortiermethoden und Sortiermethoden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
In Verbindung stehende Artikel
Mehr sehen- Eine eingehende Analyse der Bootstrap-Listengruppenkomponente
- Detaillierte Erläuterung des JavaScript-Funktions-Curryings
- Vollständiges Beispiel für die Generierung von JS-Passwörtern und die Erkennung der Stärke (mit Download des Demo-Quellcodes)
- Angularjs integriert WeChat UI (weui)
- Wie man mit JavaScript schnell zwischen traditionellem Chinesisch und vereinfachtem Chinesisch wechselt und wie Websites den Wechsel zwischen vereinfachtem und traditionellem Chinesisch unterstützen – Javascript-Kenntnisse