Tri bulle
Le principe de la bulle est de faire de l'élément le plus grand ou du plus petit élément "flottant"
Insérer le tri, le tri, le tri rapide, le tri des bulles sont tous
Idées
Comparez les deux numéros adjacents un par un, mettez les décimales devant et les grands nombres à l'arrière.
Étape 1: Comparez les premier et deuxième nombres, mettez la décimale avant et le grand nombre après. Comparez le deuxième numéro et le troisième numéro, mettez la décimale avant et après le grand nombre, continuez comme ceci jusqu'à ce que les deux derniers numéros soient comparés, mettez la décimale avant et après le grand nombre.
Étape2: Lors du deuxième voyage: commencez toujours à partir du premier logarithme (car il peut être dû à l'échange du deuxième numéro et du troisième numéro, le premier numéro n'est plus plus petit que le deuxième numéro), mettez la décimale avant et après avoir mis le grand nombre, comparer jusqu'à l'avant-dernier nombre (la première position est déjà la plus importante à la position avant-dernier). À la fin du deuxième voyage, un nouveau nombre maximum est obtenu à l'avant-dernière position (en fait le deuxième plus grand nombre de toute la séquence).
Si cela continue, répétez le processus ci-dessus jusqu'à ce que le tri soit finalement terminé.
Étant donné que les décimales sont toujours placées vers l'avant et que de grands nombres sont placés vers l'arrière pendant le processus de tri, ce qui équivaut à la montée des bulles, il est appelé tri des bulles.
Effet d'animation de tri à bulles
Implémentation: Ce code est relativement simple et est le code le plus fondamental et le plus basique de l'algorithme. . .
Trois choses à noter
1. La méthode d'échange de classes peut être résolue en javascript avec a = [b, b = a] [0].
remplacer
La copie de code est la suivante:
var, a, b, temp
temp = a;
a = b;
b = temp
Cette méthode d'échange
2. Faites attention à la cache des variables de boucle, où la longueur est mise en cache
3. Faites attention à la boucle intégrée, qui est à comparer du premier numéro au nème dernier numéro, et n est le numéro d'étape de comparaison
fonction bubblesort (array) {var l = array.length; for (var i = 0; i <l; i ++) {// Le nombre d'étapes comparés est la longueur du tableau pour (var j = 0; j <li; j ++) {// Le nombre d'échanges en ligne est comparé à partir du premier nombre à la longueur totale des nombres de la dernière), n est le pas de comparaison si (Array [j] [j - j - 1) est {array [j] = [array [j - 1], array [j - 1] = array [j]] [0] // échange des éléments ici}} pour (var k = 0; k <l; k ++) {console.log (array [k] + ",");} console.log ('Ceci est le' + (i + 1) + 'ordre')}} [6,54,6,22,5,7,8,2,34]; Bubblesort (a);Effet d'animation
Tri insertion
C'est très simple, ce sont les étapes pour nous à toucher et à insérer des cartes!
Idées:
1 Tout d'abord, disons que nous avons touché une carte, et toutes les cartes dans nos mains sont réglées sur vide = [] a touché une poussée (arr [0])
2 Sortez la carte suivante, définissez-la sur A, scannez de l'arrière vers l'avant dans toutes nos cartes vides (déjà triées)
3 Si la carte dans votre main est vide [vide.length-n] (tri) est supérieure à l'élément nouvel
4repeat Étape 3 jusqu'à ce que la carte triée vide [vide.length-n] soit inférieure ou égale à un
5 Insérez A dans cette position vide [vide.length-n] = A
6 Répétez l'étape 2
Cependant, le code JavaScript est encore un peu difficile à implémenter, le code est le suivant:
Fonction INSERT (arr) {var l = arr.length; var vide = []; // Tableau vide, indiquant notre main vide.push (arr [0]); // touchons d'abord une image pour (var i = 1; i <l; i ++) {// Notez que le point de départ ici est 1, car nous en avons touché un! if (arr [i]> vide [vide.length - 1]) {vide [vide.length] = arr [i]} // s'il est plus grand que le tableau ordonné vide, mettez-le directement à la fin pour (var j = vide.length; j> 0 && arr [i] <vide [j - 1]; j--) {// compare de la valeur maximale avec Arr afin de commercialiser le Arr. Lorsque vous arrosez un certain tableau ordonné, il n'est pas nécessaire de le déplacer. vide [j] = vide [j - 1]; // déplacer vide [j - 1] = arr [i]; // Mettez la valeur à la position vide} // console.log (vide)} return vide}Ensuite, le point de connaissance le plus important ici est le symbole &&, qui signifie "et", c'est-à-dire que les conditions des deux côtés doivent être remplies avant que l'expression ne soit établie.
Le symbole && peut également remplacer si, par exemple, si (a) {fun ()} est égal à A && b
Un autre point très important
En supposant que le tableau est arr, alors son "dernier élément" est arr [arr.length-1].
Trier l'animation
Tri de sélection
Il s'agit également d'un algorithme de tri simple.
Idées:
Trouvez le plus petit élément - jetez-le dans le tableau - retrouvez le petit à nouveau - jetez-le dans le tableau, etc.
Tout d'abord, trouvez le plus petit élément du réseau non trié. La méthode que vous trouvez peut utiliser les moyennes de jugement et d'affectation continues, c'est-à-dire: que le premier tableau d'élément [0] du tableau soit le plus petit élément, alors le numéro de séquence de "l'élément minimum" dans le tableau est 0.
Ensuite, itérez sur le tableau. Si le deuxième élément du tableau est plus petit que celui-ci, le deuxième élément est le plus petit élément et mettez à jour "0" à "1".
Après la traversée, nous savons que l'indice du plus petit élément de cette série est "N"; Il est retiré et stocké à la position de départ de la séquence de tri (tableau [n])
Ensuite, continuez à chercher le plus petit élément des éléments non triés restants, puis placez-le à la fin de la séquence triée. Notez que l'indice de la traversée commence à partir de 1 pour le moment. Parce que nous avons déjà choisi un plus petit élément.
Et ainsi de suite jusqu'à ce que tous les éléments soient triés.
Fonction SelectSort (Array) {var min; var l = array.length; // longueur cache pour (var i = 0; i <l; i ++) {// Démarrer la boucle, 1 fois au total, et vous pouvez trouver L des éléments min = i; // supposons que le premier est le plus petit élément pour (var j = i + 1; j <l; j ++) {// start Loop de la première, i si (Array [Min]> Array [J]) // juger si le Min = j; // ultérieur à mettre à jour l'indice "minimum"} if (min! = i) {// Parce que ici, parce qu'il fonctionne dans le même tableau, vous pouvez échanger directement des éléments. Par exemple, le premier élément du tableau est I, puis j'ai trouvé que le plus petit élément est le tableau [min], donc j'ai besoin d'échanger cette min avec i. Et ainsi de suite. array [i] = [array [min], array [min] = array [i]] [0]; // échange des éléments}} return array;}Ce qui est encore noté ici est la méthode d'écriture du tableau d'échange [i] = [array [min], array [min] = array [i]] [0]
Il est facile d'échanger un tableau [i] et un tableau [min] ~
Trier l'animation
Tri rapide
Le tri rapide est l'algorithme de tri le plus puissant actuellement, qui tire parti de l'idée de la récursivité.
Idées
Choisir un élément du tableau s'appelle "Benchmark". Cela peut être sélectionné directement à l'aide de la longueur / 2
Itérer à travers le tableau, tous les éléments avec une valeur de référence inférieure à la référence sont placés devant la référence, et tous les éléments avec plus de valeur de référence sont placés derrière la référence (le même nombre peut être utilisé de chaque côté). En termes simples, l'homme se tient à gauche et la femme se tient à droite. .
Ensuite, nous obtenons un tableau de tableau = tableau Larray composé de pièces plus petites que le benchmark + tableau Rarray composé de pièces plus grandes que la référence.
Ensuite, nous n'avons qu'à "même" processus Larray et Rarray ~
Cela nécessite l'utilisation de l'écriture de récursivité. Après le traitement, Larray est divisé en référence de Larray, qui est plus petit que la référence de Larray et plus grande que la référence de Larray. .
Ensuite, nous continuons à faire des choses, l'homme se tient à gauche et la femme se tient à droite. .
Jusqu'à ce que nous constatons que la longueur de Larray est devenue 1, ce qui n'est pas suffisant pour être divisé à nouveau, nous pensons que le tri est terminé.
fonction Quicksort (arr) {var l = arr.length; // longueur de tableau en cache if (arr.length <= 1) {return arr}; // Si la longueur de Larray et Rarray que nous obtenons est inférieure à 1, il n'est pas nécessaire de s'aligner ~ var num = math.floor (arr.length / 2); // Choisissez le nombre au milieu du tableau. Notez que la longueur / 2 n'est pas nécessairement un entier. Utilisez math.floor pour rondelle var numvalue = arr.splice (num, 1) [0]; // Utilisez la méthode d'épissage pour prendre un élément, faites attention à la syntaxe var gauche = []; // Créer le conteneur de référence gauche var droit = []; // Créer le conteneur de référence droit pour (var i = 0; i <l; i + = 1) {// Démarrer le trapinage de l'arrivée Arrat arr [i] Left.push (arr [i]): droite.push (arr [i]); // l'homme se tient à gauche et la femme se tient à droite. . } return Quicksort (gauche) .concat ([numValue], Quicksort (à droite)) // Récursivement, continuez à fonctionner sur les tableaux gauche et droit. }Effet d'animation:
Notez ici que bien que l'arr.splice (num, 1) ne dessine qu'un seul nombre, le résultat de l'épissage est également un tableau, ce qui nécessite [0], sinon le résultat sera étrangement un tas de tableaux de tableaux (1). . .
référence d'épissage: //www.vevb.com/w3school/js/jsref_splice.htm
Math.floor est une référence pour les objets mathématiques //www.vevb.com/w3school/js/js_obj_math.htm
Qu'est-ce que la récursivité: http://baike.baidu.com/view/96473.htm
En plus du tri rapide, les quatre algorithmes ci-dessus sont tous des algorithmes de tri simples, et ces quatre algorithmes sont très fréquemment pris lors des entretiens ~
Il est toujours important de souligner ici que l'algorithme ci-dessus utilise beaucoup de connaissances pertinentes sur les boucles et les tableaux, vous devez donc la mémoriser!