J'ai été exposé à diverses notions d'algorithmes depuis que j'ai appris la structure des données, mais je ne l'ai jamais pratiqué depuis que j'ai terminé l'examen. Quand je me développais, j'ai également vérifié quand je l'ai utilisé. Maintenant j'apprends JavaScript. Je prends ce temps pour organiser divers algorithmes de base et écrire du code dans la syntaxe JS et PHP respectivement.
1. Tri à bulles
Principe: Comparez les nombres adjacents en paires et échangez-les dans l'ordre de petit à grand ou grand à petit. Après un voyage, le plus grand ou le plus petit nombre est échangé au dernier chiffre, puis les comparer et les échanger du début jusqu'à la fin du dernier chiffre.
Complexité du temps: cas moyen: o (n2) Meilleur cas: o (n) pire cas: o (n2)
Complexité de l'espace: O (1)
Stabilité: stable
// Array var syntaxe JavaScript = [23,0,32,45,56,75,43,0,34]; pour (var i = 0; i <array.length; i ++) {var issort = true; pour (var j = 0; j <array.length - 1 - i; j ++) {if (array [j]> array [j + 1]) {issort = false; var temp = array [j]; Array [J] = Array [J + 1]; Array [J + 1] = temp; }} if (issort) {break; }} console.log (array); <? PHP $ Array = [23,0,32,45,56,75,43,0,34]; pour ($ i = 0; $ i <count ($ array); $ i ++) {$ issort = true; pour ($ j = 0; $ j <count ($ array) - 1; $ j ++) {if ($ array [$ j]> $ array [$ j + 1]) {$ issort = false; $ temp = $ array [$ j]; $ array [$ j] = $ array [$ j + 1]; $ array [$ j + 1] = $ temp; }} if ($ issort) {break; }} var_dump ($ array) ;?>2. Tri de sélection simple
Principe: En comparant les mots clés NI, sélectionnez l'enregistrement avec le plus petit mot-clé à partir des enregistrements N-I + 1 et échangez-le avec i (1 <= i <= n) th enregistre. Les performances du tri de sélection simple sont légèrement meilleures que le tri des bulles.
Complexité du temps: cas moyen: o (n2) Meilleur cas: o (n) pire cas: o (n2)
Complexité de l'espace: O (1)
Stabilité: instable
// array var javascript = [23,0,32,45,56,75,43,0,34]; pour (var i = 0; i <array.length - 1; i ++) {var pos = i; pour (var j = i + 1; j <array.length; j ++) {if (array [j] <array [pos]) {pos = j; }} var temp = array [i]; array [i] = array [pos]; Array [pos] = temp; } console.log (array); <? PHP $ Array = [23,0,32,45,56,75,43,0,34]; pour ($ i = 0; $ i <count ($ array); $ i ++) {$ pos = $ i; pour ($ j = $ i + 1; $ j <count ($ array); $ j ++) {if ($ array [$ j] <$ array [$ pos]) {$ pos = $ j; }} $ temp = $ array [$ i]; $ array [$ i] = $ array [$ pos]; $ array [$ pos] = $ temp; } var_dump ($ array) ;?>3. Insérer directement le tri
Principe: insérez un enregistrement dans le tableau ordonné trié, obtenant ainsi un nouveau tableau ordonné avec 1 incréments d'enregistrements. Autrement dit, traitez d'abord le premier enregistrement de la séquence comme une sous-séquence ordonnée, puis insérez-les un par un à partir du deuxième enregistrement jusqu'à ce que la séquence entière soit ordonnée. Meilleure performance que la méthode de bulle et le tri de sélection
Complexité du temps: cas moyen: o (n2) Meilleur cas: o (n) pire cas: o (n2)
Complexité de l'espace: O (1)
Stabilité: stable
// array var javascript = [23,0,32,45,56,75,43,0,34]; pour (var j = 0; j <array.length; j ++) {var key = array [j]; var i = j - 1; while (i> -1 && array [i]> key) {array [i + 1] = array [i]; i = i - 1; } array [i + 1] = key; } console.log (array); <? Php // insérer directement le tri de $ Array = [23,0,32,45,56,75,43,0,34]; pour ($ i = 0; $ i <count ($ array); $ i ++) {$ key = $ array [$ i]; $ J = $ i - 1; while ($ j> -1 && $ array [$ j]> $ key) {$ array [$ j +1] = $ array [$ j]; $ j = $ j - 1; } $ array [$ j + 1] = $ key; } var_dump ($ array) ;?>4. Sort rapide
Principe: grâce à un tri, les données à tri est divisée en deux parties indépendantes, et toutes les données en partie sont plus petites que toutes les données de l'autre partie, puis les deux parties des données sont rapidement triées selon cette méthode. L'ensemble du processus de tri peut être effectué récursivement pour réaliser les données entières devenant une séquence ordonnée.
Complexité du temps: cas moyen: o (nlog2n) Meilleur cas: o (nlog2n) pire cas: o (n2)
Complexité de l'espace: o (nlog2n)
Stabilité: instable
// array var rapide JavaScript = [23,0,32,45,56,75,43,0,34]; var Quicksort = fonction (arr) {if (arr.length <= 1) {return arr; } // Vérifiez le nombre d'éléments dans le tableau, s'il est inférieur ou égal à 1, il sera retourné. var pivotIndex = math.floor (arr.length / 2); // var pivot = arr.splice (pivotIndex, 1) [0]; // sélectionner "Benchmark" (pivot) et le séparer du tableau d'origine, var gauche = []; // définir deux tableaux vides pour stocker deux sous-ensembles d'une gauche et un droit droit droit = []; for (var i = 0; i <arr.length; i ++) // transveller le tableau, mettre des éléments plus petits que le "Benchmark" dans le sous-ensemble à gauche et des éléments plus grands que le benchmark dans le sous-ensemble à droite. {if (arr [i] <pivot) {Left.push (arr [i]); } else {droite.push (arr [i]); }} return Quicksort (gauche) .concat ([pivot], Quicksort (à droite)); // répétez ce processus en continu pour obtenir le tableau trié. }; var newArray = Quicksort (array); Console.log (NewArray); <? PHP $ Array = [23,0,32,45,56,75,43,0,34]; fonction Quick_sort ($ arr) {// Déterminez d'abord si vous devez continuer $ length = count ($ arr); if ($ longueur <= 1) {return $ arr; } $ base_num = $ arr [0]; // Sélectionnez une règle pour sélectionner le premier élément // initialiser deux tableaux $ Left_Array = Array (); // $ droit_array moins que le souverain = array (); // pour ($ i = 1; $ i <$ la longueur; $ i ++) {// Toussure à l'exception de la règle et les mettent en deux arlations selon la relation de taille si ($ Base_NUM> $ arr [$ i]) {// mettre dans le tableau gauche $ Left_Array [] = $ arr [$ i]; } else {// mis dans la droite $ droite_array [] = $ arr [$ i]; }} // puis la même méthode de tri pour les tableaux gauche et droit respectivement // appelant cette fonction récursivement et enregistrant le résultat $ Left_Array = Quick_sort ($ Left_Array); $ right_array = Quick_sort ($ right_array); // fusionne la règle de gauche vers le retour à droite array_merge ($ Left_Array, array ($ base_num), $ right_array); } $ newArray = Quick_sort ($ array); var_dump ($ newarray) ;?>5. HOLL SORT
Principe: Tout d'abord, divisez toute la séquence d'enregistrements à tris en plusieurs sous-séquences pour l'insertion directe et le tri. Lorsque les enregistrements de toute la séquence sont "essentiellement ordonnés", insérez et triez les enregistrements entiers en séquence. .
Complexité du temps: cas moyen: o (n√n) Meilleur cas: o (nlog2n) pire: o (n2)
Complexité de l'espace: O (1)
Stabilité: instable
// Array Var Toi Var de JavaScript = [23,0,32,45,56,75,43,0,34]; var shellSort = function (arr) {var longueur = arr.length; var h = 1; while (h <longueur / 3) {h = 3 * h + 1; // définir l'intervalle} while (h> = 1) {for (var i = h; i <longueur; i ++) {for (var j = i; j> = h && arr [j] <arr [jh]; j- = h) {var temp = arr [jh]; arr [jh] = arr [j]; arr [j] = temp; }} h = (h-1) / 3; } return arr; } var newArray = shellSort (array); Console.log (NewArray); <? PHP // HILL SORT $ Array = [23,0,32,45,56,75,43,0,34]; Fonction ShellSort ($ arr) {$ Length = Count ($ arr); $ h = 1; tandis que ($ h <$ length / 3) {$ h = 3 * $ h + 1; // définir l'intervalle} while ($ h> = 1) {for ($ i = $ h; $ i <$ length; $ i ++) {for ($ j = $ i; $ j> = $ h && $ arr [$ j] <$ arr [$ j]; $ j - = $ h) {$ temp = temp = $ ar [$ j]; $ j - = $ h) { $ arr [$ j- $ h] = $ arr [$ j]; $ arr [$ j] = $ temp; }} $ h = ($ h-1) / 3; } return $ arr; } $ newArray = shellSort ($ array); var_dump ($ newarray)?>6. Commande
Principe: En supposant que la séquence initiale contient n enregistrements, il peut être considéré comme n sous-séquences ordonnées, chaque sous-séquence a une longueur de 1, puis fusionnée par paires pour obtenir (le plus petit entier pas moins de n / 2) sous-séquences ordonnées avec des longueurs de 2 ou 1, et fusionnée par paires ... répéter de cette façon jusqu'à ce qu'une séquence ordonnée soit obtenue.
Complexité temporelle: cas moyen: o (nlog2n) Meilleur cas: o (nlog2n) pire cas: o (nlog2n)
Complexité de l'espace: O (1)
Stabilité: stable
// la fonction de tri de fusion javascript isArray1 (arr) {if (object.prototype.toString.call (arr) == '[Array d'objet]') {return true; } else {return false; }} fonction fusion (gauche, droite) {var result = []; if (! IsArray1 (gauche)) {Left = [Left]; } if (! IsArray1 (à droite)) {droite = [droite]; } while (Left.length> 0 && droite.length> 0) {if (Left [0] <droite [0]) {result.push (Left.shift ()); } else {result.push (droite.shift ()); }} return result.concat (gauche) .Concat (à droite); } fonction Mergesort (arr) {var len = arr.length; var lim, work = []; var i, j, k; if (len == 1) {return arr; } pour (i = 0; i <len; i ++) {work.push (arr [i]); } work.push ([]); pour (lim = len; lim> 1;) {// lim est la longueur de regroupement pour (j = 0, k = 0; k <lim; j ++, k = k + 2) {work [j] = fusion (work [k], work [k + 1]); } work [j] = []; lim = math.floor ((lim + 1) / 2); } Retour Work [0]; } var array = [23,0,32,45,56,75,43,0,34]; Console.log (Mergesort (Array)); <? Php // Comprendre la fonction de tri Mergesort (& $ arr) {$ len = count ($ arr); // trouver la longueur du tableau msort ($ arr, 0, $ len-1); } // Le programme qui implémente réellement la fonction de tri MSORT (& $ arr, $ Left, $ droite) {if ($ gauche <$ droite) {// Indique qu'il y a 1 élément supplémentaire dans la sous-séquence, puis il est nécessaire de se diviser, de trier séparément, de fusionner // calculer la position divisée, la longueur / 2 aller à l'ensemble $ Centre = Floor (($ gauche + $) / 2); // L'appel récursif trie à nouveau le côté gauche: MSORT ($ arr, $ Left, $ Center); // Appel récursivement pour trier le côté droit à nouveau MSORT ($ arr, $ Center + 1, $ à droite); // fusionner les résultats de tri MergeArray ($ arr, $ gauche, $ Centre, $ à droite); }} // Combinez deux numéros ordonnés dans une fonction de tableau ordonnée MergeArray (& $ arr, $ gauche, $ Center, $ droite) {// Définissez deux marques de position de départ $ a_i = $ gauche; $ b_i = $ Center + 1; while ($ a_i <= $ Center && $ b_i <= $ droit) {// Lorsque ni le tableau A ni le tableau B traverse la limite if ($ arr [$ a_i] <$ arr [$ b_i]) {$ temp [] = $ arr [$ a_i ++]; } else {$ temp [] = $ arr [$ b_i ++]; }} // juger si tous les éléments du tableau A sont utilisés. Sinon, insérez tous les éléments dans le tableau C: while ($ a_i <= $ Center) {$ temp [] = $ arr [$ a_i ++]; } // juger si tous les éléments du tableau B sont utilisés. Sinon, insérez tous les éléments dans le tableau C: while ($ b_i <= $ droit) {$ temp [] = $ arr [$ b_i ++]; } // Écrivez la pièce triée dans $ arc dans $ arr: for ($ i = 0, $ len = count ($ temp); $ i <$ len; $ i ++) {$ arr [$ Left + $ i] = $ temp [$ i]; }} $ arr = Array (23,0,32,45,56,75,43,0,34); Mergesort ($ arr); var_dump ($ arr) ;?>7. Tri de tas
Principe: le tri du tas est une méthode de tri à l'aide du tas. L'idée de base est: construire la séquence à tri en grande tas supérieure. À l'heure actuelle, la valeur maximale de la séquence entière est le nœud racine du haut du tas. Retirez-le (en fait, il s'agit de l'échanger avec l'élément final du réseau de tas, et l'élément final est la valeur maximale), puis reconstruire les séquences N-1 restantes en un tas, de sorte que la valeur sous-maximale de n éléments sera obtenue. Cela entraînera une exécution répétée et une séquence ordonnée peut être obtenue.
Complexité temporelle: cas moyen: o (nlog2n) Meilleur cas: o (nlog2n) pire cas: o (nlog2n)
Complexité de l'espace: O (1)
Stabilité: instable
// THEAP VAR VAR TOR VAR TORS = [23,0,32,45,56,75,43,0,34]; fonction heapsort (array) {for (var i = math.floor (array.length / 2); i> = 0; i--) {heapadJust (array, i, array.length - 1); // Créez le tableau du tableau dans un grand tas supérieur} pour (i = array.length - 1; i> = 0; i--) {/ * échangez le nœud racine * / var temp = array [i]; array [i] = array [0]; Array [0] = temp; / * Le tableau restant continue d'être intégré à un grand tas supérieur * / tasaDJust (tableau, 0, i - 1); } Return Array; } fonction tasAapAdJust (array, start, max) {var temp = array [start]; // temp est la valeur du nœud racine pour (var j = 2 * start; j <max; j * = 2) {if (j <max && array [j] <array [j + 1]) {// Obtenez l'enfant plus ancien ++ j; } if (temp> = array [J]) Break; array [start] = array [j]; start = j; } array [start] = temp; } var newArray = heapsort (array); Console.log (NewArray); <? Php // Fonction de tri de tas Heapsort (& $ arr) {#Initheap ($ arr, 0, count ($ arr) - 1); #Start échangez les nœuds de tête et de queue, et réduisez un nœud d'extrémité à la fois et ajustez le tas jusqu'à ce qu'il reste un élément pour ($ end = count ($ arr) - 1; $ end> 0; $ end--) {$ temp = $ arr [0]; $ arr [0] = $ arr [$ end]; $ arr [$ end] = $ temp; ajustNodes ($ arr, 0, $ end - 1); }} #Initialize le tas maximum, commencez à partir du dernier nœud non-feuille, et le dernier nœud non-feuille est numéroté sous forme de longueur de tableau / 2 fonction d'arrondage initheap (& $ arr) {$ len = count ($ arr); pour ($ start = plancher ($ len / 2) - 1; $ start> = 0; $ start--) {ajushistNodes ($ arr, $ start, $ len - 1); }} # AjusterNodes # @ param $ array à ajuster # @ param $ Démarrer les coordonnées du nœud parent à ajuster # @ param $ fin les coordonnées du nœud final à ajuster ajushistNodes (& $ arr, $ start, $ end) {$ maxinx = $ start; $ Len = $ end + 1; #La longueur de la pièce à ajuster $ LeftChildInx = ($ start + 1) * 2 - 1; #Left coordonnée enfant $ RightChildInx = ($ start + 1) * 2; #Right Child Coordonnées # Si la pièce à régler a un enfant gauche if ($ LeftChildInx + 1 <= $ Len) {#get la coordonnée du nœud minimum if ($ arr [$ maxinx] <$ arr [$ LeftChildInx]) {$ maxinx = $ LeftChildInx; } #Si la pièce à ajuster a un nœud enfant correct if ($ RightChildInx + 1 <= $ len) {if ($ arr [$ maxinx] <$ arr [$ RightChildInx]) {$ maxinx = $ RightChildInx; }}} #Swap Node parent et nœud maximum if ($ start! = $ Maxinx) {$ temp = $ arr [$ start]; $ arr [$ start] = $ arr [$ maxinx]; $ arr [$ maxinx] = $ temp; # Si le nœud enfant après l'échange a des nœuds enfants, continuez à ajuster if (($ maxinx + 1) * 2 <= $ len) {ajushiDodes ($ arr, $ maxinx, $ end); }}} $ arr = Array (23,0,32,45,56,75,43,0,34); Heapsort ($ arr); var_dump ($ arr) ;?>8. Tri de la cardinalité
Principe: coupez les entiers en différents nombres par chiffres, puis comparez-les séparément par chaque chiffre. Étant donné que les entiers peuvent également exprimer des chaînes (telles que des noms ou des dates) et des nombres à virgule flottante dans des formats spécifiques, le tri radice n'est pas seulement utilisé pour les entiers.
Complexité du temps: cas moyen: o (d (r + n)) Meilleur cas: o (d (n + rd)) pire cas: o (d (r + n)) r: cardinalité des mots clés d: longueur n: nombre de mots clés
Complexité de l'espace: O (Rd + N)
Stabilité: stable
<? PHP #blassorting, ici seuls les entiers positifs sont triés. Quant aux nombres négatifs et aux nombres de points flottants, un complément est nécessaire. Vous êtes intéressé à étudier le tri #Counting # @ param $ array à tri count ($ arr); $ i ++) {$ arr_temp [$ i] = get_specific_digit ($ arr [$ i], $ digit_num); }} else {$ arr_temp = $ arr; } $ max = max ($ arr); $ time_arr = array (); #Storage Array of Elements occurrences # Initialize Occurrences Array for ($ i = 0; $ i <= $ max; $ i ++) {$ time_arr [$ i] = 0; } #Statiser les occurrences de chaque élément pour ($ i = 0; $ i <count ($ arr_temp); $ i ++) {$ time_arr [$ arr_temp); $ i ++) {$ time_arr [$ arr_temp [$ i]] ++; } #Statify les occurrences de chaque élément qui en est plus petit ou égal pour ($ i = 0; $ i <count ($ time_arr) - 1; $ i ++) {$ time_arr [$ i + 1] + = $ time_arr [$ i]; } #Sort le tableau en utilisant le nombre d'occurrences pour ($ i = count ($ arr) - 1; $ i> = 0; $ i--) {$ trid_arr [$ time_arr [$ arr_temp [$ i]] - 1] = $ arr [$ i]; $ time_arr [$ arr_temp [$ i]] -; } $ arr = $ trid_arr; ksort ($ arr); #Ignore la perte d'efficacité du tri des clés cette fois} #calculate le nombre de bits d'une certaine fonction de nombre get_digit ($ numéro) {$ i = 1; while ($ numéro> = pow (10, $ i)) {$ i ++; } return $ i; } #get le numéro de chiffre i -th d'un nombre de la fonction à un chiffre get_specific_digit ($ num, $ i) {if ($ num <pow (10, $ i - 1)) {return 0; } Floo Retour ($ num% pow (10, $ i) / pow (10, $ i - 1)); } #Black Tri, comptez le tri comme fonction de processus de sous-sort radix_sort (& $ arr) {#First Trouvez le plus grand chiffre du tableau $ max = max ($ arr); $ max_digit = get_digit ($ max); pour ($ i = 1; $ i <= $ max_digit; $ i ++) {compting_sort ($ arr, $ i); }} $ arr = Array (23,0,32,45,56,75,43,0,34); radix_sort ($ arr); var_dump ($ arr) ;?>Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.