Maison interface Web js tutoriel Javascript中的常见排序算法_javascript技巧

Javascript中的常见排序算法_javascript技巧

May 16, 2016 pm 07:16 PM
排序算法

具体代码及比较如下所示:

复制代码 代码如下:

nbsp;html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 
 
 
 常见排序算法 之 JavaScript版  
 
 
 
<script> <BR> Array.prototype.swap = function(i, j) <BR> { <BR> var temp = this[i]; <BR> this[i] = this[j]; <BR> this[j] = temp; <BR> } <BR> Array.prototype.bubbleSort = function() <BR> { <BR> for (var i = this.length - 1; i > 0; --i) <BR> { <BR> for (var j = 0; j < i; ++j) <BR> { <BR> if (this[j] > this[j + 1]) this.swap(j, j + 1); <BR> } <BR> } <BR> } <BR> Array.prototype.selectionSort = function() <BR> { <BR> for (var i = 0; i < this.length; ++i) <BR> { <BR> var index = i; <BR> for (var j = i + 1; j < this.length; ++j) <BR> { <BR> if (this[j] < this[index]) index = j; <BR> } <BR> this.swap(i, index); <BR> } <BR> } <BR> Array.prototype.insertionSort = function() <BR> { <BR> for (var i = 1; i < this.length; ++i) <BR> { <BR> var j = i, value = this[i]; <BR> while (j > 0 && this[j - 1] > value) <BR> { <BR> this[j] = this[j - 1]; <BR> --j; <BR> } <BR> this[j] = value; <BR> } <BR> } <BR> Array.prototype.shellSort = function() <BR> { <BR> for (var step = this.length >> 1; step > 0; step >>= 1) <BR> { <BR> for (var i = 0; i < step; ++i) <BR> { <BR> for (var j = i + step; j < this.length; j += step) <BR> { <BR> var k = j, value = this[j]; <BR> while (k >= step && this[k - step] > value) <BR> { <BR> this[k] = this[k - step]; <BR> k -= step; <BR> } <BR> this[k] = value; <BR> } <BR> } <BR> } <BR> } <BR> Array.prototype.quickSort = function(s, e) <BR> { <BR> if (s == null) s = 0; <BR> if (e == null) e = this.length - 1; <BR> if (s >= e) return; <BR> this.swap((s + e) >> 1, e); <BR> var index = s - 1; <BR> for (var i = s; i <= e; ++i) <BR> { <BR> if (this[i] <= this[e]) this.swap(i, ++index); <BR> } <BR> this.quickSort(s, index - 1); <BR> this.quickSort(index + 1, e); <BR> } <BR> Array.prototype.stackQuickSort = function() <BR> { <BR> var stack = [0, this.length - 1]; <BR> while (stack.length > 0) <BR> { <BR> var e = stack.pop(), s = stack.pop(); <BR> if (s >= e) continue; <BR> this.swap((s + e) >> 1, e); <BR> var index = s - 1; <BR> for (var i = s; i <= e; ++i) <BR> { <BR> if (this[i] <= this[e]) this.swap(i, ++index); <BR> } <BR> stack.push(s, index - 1, index + 1, e); <BR> } <BR> } <BR> Array.prototype.mergeSort = function(s, e, b) <BR> { <BR> if (s == null) s = 0; <BR> if (e == null) e = this.length - 1; <BR> if (b == null) b = new Array(this.length); <BR> if (s >= e) return; <BR> var m = (s + e) >> 1; <BR> this.mergeSort(s, m, b); <BR> this.mergeSort(m + 1, e, b); <BR> for (var i = s, j = s, k = m + 1; i <= e; ++i) <BR> { <BR> b[i] = this[(k > e || j <= m && this[j] < this[k]) ? j++ : k++]; <BR> } <BR> for (var i = s; i <= e; ++i) this[i] = b[i]; <BR> } <BR> Array.prototype.heapSort = function() <BR> { <BR> for (var i = 1; i < this.length; ++i) <BR> { <BR> for (var j = i, k = (j - 1) >> 1; k >= 0; j = k, k = (k - 1) >> 1) <BR> { <BR> if (this[k] >= this[j]) break; <BR> this.swap(j, k); <BR> } <BR> } <BR> for (var i = this.length - 1; i > 0; --i) <BR> { <BR> this.swap(0, i); <BR> for (var j = 0, k = (j + 1) << 1; k <= i; j = k, k = (k + 1) << 1) <BR> { <BR> if (k == i || this[k] < this[k - 1]) --k; <BR> if (this[k] <= this[j]) break; <BR> this.swap(j, k); <BR> } <BR> } <BR> } <BR> function generate() <BR> { <BR> var max = parseInt(txtMax.value), count = parseInt(txtCount.value); <BR> if (isNaN(max) || isNaN(count)) <BR> { <BR> alert("个数和最大值必须是一个整数"); <BR> return; <BR> } <BR> var array = []; <BR> for (var i = 0; i < count; ++i) array.push(Math.round(Math.random() * max)); <BR> txtInput.value = array.join("\n"); <BR> txtOutput.value = ""; <BR> } <BR> function demo(type) <BR> { <BR> var array = txtInput.value == "" ? [] : txtInput.value.replace().split("\n"); <BR> for (var i = 0; i < array.length; ++i) array[i] = parseInt(array[i]); <BR> var t1 = new Date(); <BR> eval("array." + type + "Sort()"); <BR> var t2 = new Date(); <BR> lblTime.innerText = t2.valueOf() - t1.valueOf(); <BR> txtOutput.value = array.join("\n"); <BR> } <BR></script> 
 
 
 
 
  
  
  
 
 
  
 
 
 随机数个数

 
 最大随机数

 
 



 
 耗时(毫秒):



 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 
 
  
 
 
 
 

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

个人理解

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

算法源码
复制代码 代码如下:

// ---------- 一些排序算法
// js 利用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(; ifor(j=0; jif(array[i] 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 stepi = i; // 记录开始位置
var stepj = 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(stepi == i){
Sort(++i, stepj);
return ;
}
// 最后一个空位留给 key
array[i] = key;
// 递归
Sort(stepi, i);
Sort(j, stepj);
}
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, step, key,
len = array.length;
for(; 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;
},
// 希尔排序
//Jun.array.shellSort(Jun.array.df(10000));
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 stepArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在维基上看到这个最优的步长 较小数组
//var stepArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1]//针对大数组的步长选择
var i = 0;
var stepArrLength = stepArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i if(stepArr[i] > len2){
continue;
}
stepSort(stepArr[i]);
}
// 排序一个步长
function stepSort(step){
//console.log(step) 使用的步长统计
var i = 0, j = 0, f, tem, key;
var stepLen = len%step > 0 ? parseInt(len/step) + 1 : len/step;

for(;i for(j=1;/*j tem = f = step * j + i;
key = array[f];
while((tem-=step) >= 0){// 依次向上查找
if(array[tem] > key){
array[tem+step] = array[tem];
}else{
break;
}
}
array[tem + step ] = key;
}
}
}
return array;
}

测试代码打包下载
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
3 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Problèmes complexes de conception expérimentale sur le marché biface de Kuaishou Problèmes complexes de conception expérimentale sur le marché biface de Kuaishou Apr 15, 2023 pm 07:40 PM

1. Contexte du problème 1. Introduction à l'expérience du marché biface Le marché biface, c'est-à-dire une plateforme, comprend deux participants, producteurs et consommateurs, et les deux parties se promeuvent mutuellement. Par exemple, Kuaishou a un producteur vidéo et un consommateur vidéo, et les deux identités peuvent se chevaucher dans une certaine mesure. L'expérimentation bilatérale est une méthode expérimentale qui combine des groupes du côté des producteurs et des consommateurs. Les expériences bilatérales présentent les avantages suivants : (1) L'impact de la nouvelle stratégie sur deux aspects peut être détecté simultanément, tels que les changements dans le DAU du produit et le nombre de personnes téléchargeant des œuvres. Les plateformes bilatérales ont souvent des effets de réseau transversaux. Plus il y a de lecteurs, plus les auteurs seront actifs, et plus les auteurs seront actifs, plus les lecteurs suivront. (2) Le débordement et le transfert d'effet peuvent être détectés. (3) Aidez-nous à mieux comprendre le mécanisme d'action. L'expérience AB elle-même ne peut pas nous dire la relation entre la cause et l'effet, seulement.

Google utilise l'IA pour briser le sceau de dix ans de l'algorithme de tri. Elle est exécutée des milliards de fois chaque jour, mais les internautes disent que c'est la recherche la plus irréaliste ? Google utilise l'IA pour briser le sceau de dix ans de l'algorithme de tri. Elle est exécutée des milliards de fois chaque jour, mais les internautes disent que c'est la recherche la plus irréaliste ? Jun 22, 2023 pm 09:18 PM

Tri | Nuka-Cola, Chu Xingjuan Les amis qui ont suivi des cours d'informatique de base doivent avoir personnellement conçu un algorithme de tri, c'est-à-dire utiliser du code pour réorganiser les éléments d'une liste non ordonnée par ordre croissant ou décroissant. C'est un défi intéressant, et il existe de nombreuses façons possibles de le relever. Beaucoup de temps a été investi pour trouver comment accomplir les tâches de tri plus efficacement. En tant qu'opération de base, les algorithmes de tri sont intégrés aux bibliothèques standard de la plupart des langages de programmation. Il existe de nombreuses techniques et algorithmes de tri différents utilisés dans les bases de code du monde entier pour organiser de grandes quantités de données en ligne, mais au moins en ce qui concerne les bibliothèques C++ utilisées avec le compilateur LLVM, le code de tri n'a pas changé depuis plus d'une décennie. . Récemment, l'équipe Google DeepMindAI a développé un

Comment filtrer et trier les données dans le développement de la technologie Vue Comment filtrer et trier les données dans le développement de la technologie Vue Oct 09, 2023 pm 01:25 PM

Comment filtrer et trier les données dans le développement de la technologie Vue Dans le développement de la technologie Vue, le filtrage et le tri des données sont des fonctions très courantes et importantes. Grâce au filtrage et au tri des données, nous pouvons rapidement interroger et afficher les informations dont nous avons besoin, améliorant ainsi l'expérience utilisateur. Cet article expliquera comment filtrer et trier les données dans Vue et fournira des exemples de code spécifiques pour aider les lecteurs à mieux comprendre et utiliser ces fonctions. 1. Filtrage des données Le filtrage des données fait référence au filtrage des données qui répondent aux exigences en fonction de conditions spécifiques. Dans Vue, on peut passer comp

Quels sont les algorithmes de tri des tableaux ? Quels sont les algorithmes de tri des tableaux ? Jun 02, 2024 pm 10:33 PM

Les algorithmes de tri de tableaux sont utilisés pour organiser les éléments dans un ordre spécifique. Les types courants d'algorithmes incluent : Tri à bulles : échangez les positions en comparant les éléments adjacents. Tri par sélection : recherchez le plus petit élément et remplacez-le par la position actuelle. Tri par insertion : insérez les éléments un par un à la bonne position. Tri rapide : méthode diviser pour mieux régner, sélectionnez l'élément pivot pour diviser le tableau. Tri par fusion : diviser pour mieux régner, tri récursif et fusion de sous-tableaux.

Swoole Advanced : Comment utiliser le multithreading pour implémenter un algorithme de tri à grande vitesse Swoole Advanced : Comment utiliser le multithreading pour implémenter un algorithme de tri à grande vitesse Jun 14, 2023 pm 09:16 PM

Swoole est un framework de communication réseau hautes performances basé sur le langage PHP. Il prend en charge la mise en œuvre de plusieurs modes IO asynchrones et de plusieurs protocoles réseau avancés. Sur la base de Swoole, nous pouvons utiliser sa fonction multi-threading pour implémenter des opérations algorithmiques efficaces, telles que des algorithmes de tri à grande vitesse. L'algorithme de tri à grande vitesse (QuickSort) est un algorithme de tri courant. En localisant un élément de référence, les éléments sont divisés en deux sous-séquences. Celles plus petites que l'élément de référence sont placées à gauche et celles supérieures ou égales à la référence. L'élément est placé à droite. Ensuite, les sous-séquences gauche et droite sont placées par récursion.

Comment implémenter une fonction d'algorithme de tri simple à l'aide de MySQL et Java Comment implémenter une fonction d'algorithme de tri simple à l'aide de MySQL et Java Sep 20, 2023 am 09:45 AM

Comment utiliser MySQL et Java pour implémenter une fonction d'algorithme de tri simple Introduction : Dans le développement de logiciels, les algorithmes de tri sont l'une des fonctions les plus basiques et les plus couramment utilisées. Cet article expliquera comment utiliser MySQL et Java pour implémenter une fonction d'algorithme de tri simple et fournira des exemples de code spécifiques. 1. Présentation des algorithmes de tri Les algorithmes de tri sont des algorithmes qui organisent un ensemble de données selon des règles spécifiques. Les algorithmes de tri couramment utilisés incluent le tri à bulles, le tri par insertion, le tri par sélection, le tri rapide, etc. Cet article utilisera le tri à bulles comme exemple pour l'expliquer et le mettre en œuvre. 2.M

Comment implémenter l'algorithme de tri par sélection en C# Comment implémenter l'algorithme de tri par sélection en C# Sep 20, 2023 pm 01:33 PM

Comment implémenter l'algorithme de tri par sélection en C# Le tri par sélection (SelectionSort) est un algorithme de tri simple et intuitif. Son idée de base est de sélectionner à chaque fois l'élément le plus petit (ou le plus grand) parmi les éléments à trier et de le placer à la fin de. la séquence triée. Répétez ce processus jusqu'à ce que tous les éléments soient triés. Apprenons-en davantage sur la façon d'implémenter l'algorithme de tri par sélection en C#, ainsi que des exemples de code spécifiques. Création d'une méthode de tri par sélection Tout d'abord, nous devons créer une méthode pour implémenter le tri par sélection. Cette méthode accepte un

Dix principaux algorithmes de tri que les programmeurs doivent maîtriser (Partie 1) Dix principaux algorithmes de tri que les programmeurs doivent maîtriser (Partie 1) Aug 15, 2023 pm 02:55 PM

Les algorithmes de tri peuvent être considérés comme quelque chose que tout programmeur doit maîtriser. Il est nécessaire de comprendre leurs principes et leur mise en œuvre. Ce qui suit est une introduction à l'implémentation Python des dix principaux algorithmes de tri couramment utilisés pour faciliter votre apprentissage.

See all articles