Maison >interface Web >js tutoriel >Exemple d'analyse de l'implémentation JavaScript de l'algorithme de tri par sélection (image)
Exemple d'analyse de l'implémentation JavaScript de l'algorithme de tri par sélection (image)
- 黄舟original
- 2017-04-15 09:31:361873parcourir
Cet article présente principalement l'algorithme de tri par sélection implémenté par JavaScript Il analyse le principe, les étapes de mise en œuvre et les compétences opérationnelles associées du tri par sélection sous forme d'exemples. peut s'y référer. Suivant
L'exemple de cet article décrit l'algorithme de tri de sélection implémenté en JavaScript. Partagez-le avec tout le monde pour votre référence. Les détails sont les suivants :
Le tri par sélection simple est la méthode de comparaison la plus familière. Son idée d'algorithme est : . from En partant du début du tableau , comparez le premier élément avec les autres éléments. Une fois tous les éléments vérifiés, le plus petit élément est placé à la première position du tableau et l’algorithme continue à partir de la deuxième position. Ce processus se poursuivra jusqu'à ce que l'avant-dernière position du tableau soit atteinte et toutes les données seront triées.
Le code est le suivant :
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript选择排序</title>
</head>
<body>
<script type="text/javascript">
function selectSort(nums){//选择排序
var min;//最小值
for(var outer=0;outer<nums.length-1;outer++){//外循环选中元素
min=outer;
for(var inner=outer+1;inner<=nums.length;++inner){
if(nums[inner]<nums[min]){//如果内循环中元素比选中元素小
min=inner;//将其标为最小元素
}//直到每次外循环的最小元素
swap(nums,outer,min);//最小值被调整到合适的位置
}
}
}
function swap(arr,i,j){//交换位置
var temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
function show(nums){//显示数组
for(var i=0;i<nums.length;i++){
document.write(nums[i]+' ');
}
document.write('<br>');
}
var nums=[6,8,0,6,7,4,3,5,5,10];
show(nums);//6 8 0 6 7 4 3 5 5 10
selectSort(nums);
show(nums);//0 3 4 5 5 6 6 7 9 10
</script>
</body>
</html>L'analyse montre que la complexité temporelle du tri par sélection simple est O(n2). L'opération principale du tri par sélection est la comparaison entre les mots-clés, donc l'amélioration du tri par sélection simple devrait commencer par la façon de réduire les comparaisons. En fait, il existe un bon exemple dans la vie réelle, celui du championnat total du jeu. Pour choisir le champion parmi 8 personnes, vous n'avez pas réellement besoin de 7+6+5=18 parties. Vous pouvez les comparer par paires, soit 11 parties. Cette méthode est appelée Tree Selection Tri. Le
Le tri par sélection par arbre est une méthode de tri par sélection basée sur l'idée d'un tournoi. Tout d'abord, comparez les mots-clés de n enregistrements par paires, puis comparez n/2 de. Les plus petits sont ensuite comparés par paires jusqu'à ce que le plus petit mot-clé soit trouvé. Il peut être représenté par un arbre binaire complet. Puisque la profondeur d'un arbre binaire complet contenant n nœuds est log2n+1, chaque sélection d'un sous-petit mot-clé ne nécessite que des opérations log2n pendant le processus de tri, donc sa complexité temporelle est O (nlog2n) , mais ce tri a l'inconvénient de prendre beaucoup de place.
Nous devons donc introduire un meilleur tri, qui est le tri par tas.
Pièce jointe : Algorithme de tri par tas
Le tri par tas ne nécessite qu'un espace de taille d'enregistrement auxiliaire , chaque enregistrement à trier n'occupe qu'un seul espace de stockage.
Le tri par tas profite de la fonctionnalité selon laquelle la clé enregistrée en haut du grand tas racine (ou du petit tas racine) est la plus grande (ou la plus petite), de sorte que l'enregistrement avec le plus grand (ou le plus petit) Le mot-clé sélectionné dans la zone non ordonnée actuelle devient Doit être simple. Prenons le gros tas comme exemple. Les opérations de base du tri sont les suivantes :
La première consiste à construire le tas. La construction du tas est le processus d'ajustement constant du tas, en commençant par len2 et en continuant jusqu'aux premiers nœuds, où len est le nombre d'éléments dans le tas. Le processus de construction d'un tas est un processus linéaire. Le processus d'ajustement du tas est toujours appelé de len2 à 0. La complexité temporelle de la construction d'un tas est O(n).
Vient ensuite le Tas d'ajustement Le tas d'ajustement est utilisé dans le processus de construction du tas et de tri du tas. L'idée est de comparer le nœud i et son nœud enfant left( i. ) et droite(i), sélectionnez la plus grande (ou la plus petite) des trois. Si la plus grande (la plus petite) valeur n'est pas le nœud i mais l'un de ses nœuds enfants, alors échangez les deux nœuds et continuez <.>Récursion. Puis
Tri par tas : Sortez le nœud racine du tas, remplacez le nœud racine par le dernier élément, continuez le processus d'ajustement du tas avec les premiers nœuds len-1, puis parlez de la suppression du nœud racine jusqu'à ce que tous les nœuds soient supprimés. La complexité temporelle de l'ajustement du tas est O(log2n)Donc, la complexité temporelle du tri du tas est O(nlog2n). Le tri par tas est un tri sur place et son espace auxiliaire est O(1). Mais il est instable (
La stabilité du tri signifie que s'il y a deux éléments identiques dans la séquence triée, leurs positions relatives ne changeront pas avant et après le tri).
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!
Articles Liés
Voir plus- Une analyse approfondie du composant de groupe de liste Bootstrap
- Explication détaillée du currying de la fonction JavaScript
- Exemple complet de génération de mot de passe JS et de détection de force (avec téléchargement du code source de démonstration)
- Angularjs intègre l'interface utilisateur WeChat (weui)
- Comment basculer rapidement entre le chinois traditionnel et le chinois simplifié avec JavaScript et l'astuce permettant aux sites Web de prendre en charge le basculement entre les compétences en chinois simplifié et traditionnel_javascript