Comment implémenter diverses méthodes de tri à l'aide de js
Ci-dessous, je partagerai avec vous un article (explication détaillée) sur les différences entre les différentes méthodes de tri et les méthodes de tri basées sur js. Il a une bonne valeur de référence et j'espère qu'il sera utile à tout le monde.
J'ai eu un caprice aujourd'hui et je voulais savoir si la méthode de tri présente des avantages par rapport aux différents tris, j'ai donc fait un test en référence aux codes d'autres personnes. Les résultats ont été surprenants. Voici le 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>La méthode ci-dessus passe le temps de test, puis analyse quelle méthode de tri permet de gagner du temps. Le temps, c'est la vie, et utiliser la bonne méthode peut gagner beaucoup de temps, en particulier lors de l'exécution de Big Data.
Premier coup d'oeil au temps nécessaire pour traiter un tableau de 10 000 longueurs :
* système de tri triSort 11
* tri à bulles bubbleSort 169
* Tri rapide quickSort 144
* Tri par insertion insertSort 139
* Hill sort shellSort 3
Test 100 000 données de tableau long :
* système de tri de triSort 63
* tri à bulles bubbleSort 16268
* tri rapide quickSort signalant directement une erreur
* tri par insertion insertSort 13026
* Hill sorting shellSort 8
Testez un tableau d'une longueur d'un million :
* système de tri tri 575
* tri à bulles heure de tri à bulles inconnue
* Tri rapide rapports de tri rapide une erreur directement
* Le tri par insertion insertSort plante directement
* Hill sort shellSort 93
Test de 10 millions de tableaux longs :
* système de tri de tri Tri 7039
* Tri à bulles bubbleSort non testé
* tri rapide quickSort non testé
* tri par insertion insertSort non testé
* Hill sort shellSort 1225
Test d'un tableau de 100 millions de long :
* le système de tri crash directement
* tri à bulles bubbleSort non testé
* tri rapide quickSort non testé
* Tri par insertion insertSort Non testé
* Hill sort shellSort 19864
J'ai finalement réussi le test, dans le pire des cas , j'ai trouvé que le tri Hill est toujours le meilleur, et c'est encore plus rapide que le tri du système. C'est vraiment surprenant. De cette façon, chacun peut voir quelle méthode doit être utilisée pour trier dans quelles circonstances
Ensuite, nous testons dans des situations aléatoires :
<!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>Tester un tableau de 10 millions de long :
* système de tri triSort 8842
* Tri à bulles bubbleSort not testé
* Tri rapide quickSort non testé
* Tri par insertion insertSort 45
* Hill sort shellSort 1133
dans inconnu Dans certaines situations et de meilleures situations, le tri par insertion est le plus efficace
Ce qui précède est ce que j'ai compilé pour tout le monde. J'espère que cela sera utile à tout le monde à l'avenir.
Articles connexes :
Explication détaillée de la séparation et de la combinaison de vue-admin et backend (flask)
Explication détaillée dans Vue +webpack Configuration de base
Expliquez la configuration de base en détail dans Vue+webpack
Comment créer une salle de discussion multi-personnes dans nodejs +environnement express
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Outils d'IA chauds
Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes
AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.
Undress AI Tool
Images de déshabillage gratuites
Clothoff.io
Dissolvant de vêtements AI
Video Face Swap
Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !
Article chaud
Outils chauds
Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit
SublimeText3 version chinoise
Version chinoise, très simple à utiliser
Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP
Dreamweaver CS6
Outils de développement Web visuel
SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)
Sujets chauds
1393
52
1207
24
Quelles sont les exigences de base pour les fonctions de langue C
Apr 03, 2025 pm 10:06 PM
Les fonctions de langue C sont la base de la modularisation du code et de la construction de programmes. Ils se composent de déclarations (en-têtes de fonction) et de définitions (corps de fonction). Le langage C utilise des valeurs pour transmettre les paramètres par défaut, mais les variables externes peuvent également être modifiées à l'aide d'adresse Pass. Les fonctions peuvent avoir ou ne pas avoir de valeur de retour et le type de valeur de retour doit être cohérent avec la déclaration. La dénomination de la fonction doit être claire et facile à comprendre, en utilisant un chameau ou une nomenclature de soulignement. Suivez le principe de responsabilité unique et gardez la simplicité de la fonction pour améliorer la maintenabilité et la lisibilité.
La différence entre H5 et mini-programmes et applications
Apr 06, 2025 am 10:42 AM
H5. La principale différence entre les mini programmes et l'application est: Architecture technique: H5 est basé sur la technologie Web, et les mini-programmes et l'application sont des applications indépendantes. Expérience et fonctions: H5 est légère et facile à utiliser, avec des fonctions limitées; Les mini-programmes sont légers et ont une bonne interactivité; Les applications sont puissantes et ont une expérience fluide. Compatibilité: H5 est compatible multiplateforme, les applets et les applications sont limités par la plate-forme. Coût de développement: H5 a un faible coût de développement, des mini-programmes moyens et une application la plus élevée. Scénarios applicables: H5 convient à l'affichage d'informations, les applets conviennent aux applications légères et les applications conviennent aux fonctions complexes.
Concept de fonction de langue C
Apr 03, 2025 pm 10:09 PM
Les fonctions de langue C sont des blocs de code réutilisables. Ils reçoivent des entrées, effectuent des opérations et renvoient les résultats, ce qui améliore modulairement la réutilisabilité et réduit la complexité. Le mécanisme interne de la fonction comprend le passage des paramètres, l'exécution de la fonction et les valeurs de retour. L'ensemble du processus implique une optimisation telle que la fonction en ligne. Une bonne fonction est écrite en suivant le principe de responsabilité unique, un petit nombre de paramètres, des spécifications de dénomination et une gestion des erreurs. Les pointeurs combinés avec des fonctions peuvent atteindre des fonctions plus puissantes, telles que la modification des valeurs de variables externes. Les pointeurs de fonctions passent les fonctions comme des paramètres ou des adresses de magasin, et sont utilisées pour implémenter les appels dynamiques aux fonctions. Comprendre les fonctionnalités et les techniques des fonctions est la clé pour écrire des programmes C efficaces, maintenables et faciles à comprendre.
Comment définir la protection des mots de passe pour l'exportation PDF sur PS
Apr 06, 2025 pm 04:45 PM
Exporter PDF protégé par mot de passe dans Photoshop: ouvrez le fichier image. Cliquez sur "Fichier" & gt; "Export" & gt; "Exporter en PDF". Définissez l'option "Sécurité" et entrez le même mot de passe deux fois. Cliquez sur "Exporter" pour générer un fichier PDF.
Pourquoi avez-vous besoin d'appeler Vue.User (VUerouter) dans le fichier index.js dans le dossier du routeur?
Apr 05, 2025 pm 01:03 PM
La nécessité d'enregistrer VUerouter dans le fichier index.js dans le dossier du routeur Lors du développement d'applications VUE, vous rencontrez souvent des problèmes de configuration de routage. Spécial...
Quelles sont les différences et les connexions entre C et C #?
Apr 03, 2025 pm 10:36 PM
Bien que C et C # aient des similitudes, ils sont complètement différents: C est une gestion manuelle de la mémoire manuelle et un langage dépendant de la plate-forme utilisé pour la programmation système; C # est un langage orienté objet, des ordures et un langage indépendant de la plate-forme utilisé pour le bureau, l'application Web et le développement de jeux.
Comment utiliser XPath pour rechercher à partir d'un nœud DOM spécifié en JavaScript?
Apr 04, 2025 pm 11:15 PM
Explication détaillée de la méthode de recherche XPATH sous les nœuds DOM en JavaScript, nous devons souvent trouver des nœuds spécifiques de l'arbre Dom basé sur les expressions XPath. Si vous avez besoin de ...
La différence dans les résultats de sortie de Console.log: Pourquoi les mêmes variables ont-elles des méthodes d'impression différentes mais des résultats différents?
Apr 04, 2025 am 11:48 AM
Une discussion approfondie des différences de console. La sortie de la log dans cet article analysera les raisons pour lesquelles les résultats de sortie de la fonction Console.log dans un morceau de code sont différents. Les extraits de code impliquent une résolution des paramètres URL ...
