Les entretiens écrits impliquent souvent divers algorithmes. Cet article présente brièvement certains algorithmes couramment utilisés et les implémente en JavaScript.
1. Insérer le tri
1) Introduction à l'algorithme
La description de l'algorithme du sort d'insertion est un algorithme de tri simple et intuitif. Il fonctionne en construisant une séquence ordonnée, pour des données non triées, en scannant vers l'arrière et en avant dans la séquence triée, trouvez la position correspondante et insérez-la. Dans la mise en œuvre du tri des insertions, le tri sur place est généralement utilisé (c'est-à-dire que l'espace supplémentaire d'O (1) est requis), donc pendant le processus de numérisation de l'arrière à l'avant, les éléments triés doivent être déplacés à plusieurs reprises pour fournir un espace d'insertion pour les derniers éléments.
2) Description et implémentation de l'algorithme
D'une manière générale, le tri des insertions est mis en œuvre sur un tableau utilisant en place. L'algorithme spécifique est décrit comme suit:
À partir du premier élément, l'élément peut être considéré comme ayant été trié;
Sortez l'élément suivant et scannez en arrière et en avant dans la séquence d'éléments déjà triée;
Si l'élément (trié) est supérieur au nouvel élément, déplacez l'élément vers la position suivante;
Répétez l'étape 3 jusqu'à ce que l'élément trié se trouve lorsque le nouvel élément est inférieur ou égal;
Après avoir inséré un nouvel élément dans cette position;
Répétez les étapes 2 à 5.
Implémentation du code JavaScript:
fonction insertionsort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {for (var i = 1; i <array.length; i ++) {var key = array [i]; var j = i - 1; while (j> = 0 && array [j]> key) {array [j + 1] = array [j]; J-; } Array [j + 1] = key; } Return Array; } else {return 'array n'est pas un tableau!'; }}3) Analyse des algorithmes
Meilleur cas: les tableaux d'entrée sont triés par ordre croissant. T (n) = o (n)
Pire des cas: le tableau d'entrée est trié par ordre décroissant. T (n) = o (n2)
Moyenne: t (n) = o (n2)
Deux, triage d'insertion binaire
1) Introduction à l'algorithme
Le tri binaire-insert-sort est un algorithme de tri qui apporte des modifications mineures à l'algorithme de tri à l'insertion directe. La plus grande différence entre celle-ci et l'algorithme de tri insertion direct est que lorsque vous recherchez des positions d'insertion, la méthode de recherche binaire est utilisée, ce qui a une certaine amélioration de la vitesse.
2) Description et implémentation de l'algorithme
D'une manière générale, le tri des insertions est mis en œuvre sur un tableau utilisant en place. L'algorithme spécifique est décrit comme suit:
À partir du premier élément, l'élément peut être considéré comme ayant été trié;
Sortez l'élément suivant et trouvez la position du premier nombre plus grand que dans la séquence d'éléments déjà triée;
Après avoir inséré un nouvel élément dans cette position;
Répétez les deux étapes ci-dessus.
Implémentation du code JavaScript:
fonction binaraninsertionsort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {for (var i = 1; i <array.length; i ++) {var key = array [i], gauche = 0, droite = i - 1; while (gauche <= droit) {var middle = paSeInt ((gauche + droit) / 2); if (key <array [middle]) {droite = middle - 1; } else {Left = middle + 1; }} pour (var j = i - 1; j> = gauche; j--) {array [j + 1] = array [j]; } array [gauche] = key; } Return Array; } else {return 'array n'est pas un tableau!'; }}3) Analyse des algorithmes
Meilleur cas: t (n) = o (nlogn)
Pire des cas: t (n) = o (n2)
Moyenne: t (n) = o (n2)
3. Sélectionnez le tri
1) Introduction à l'algorithme
SELECTION-SORT est un algorithme de tri simple et intuitif. Comment cela fonctionne: trouvez d'abord le plus petit (grand) élément de la séquence non triée, stockez-le à la position de départ de la séquence triée, puis continuez à rechercher le plus petit (grand) élément des éléments non triés restants, puis le placez à la fin de la séquence triée. Et ainsi de suite jusqu'à ce que tous les éléments soient triés.
2) Description et implémentation de l'algorithme
La sélection directe de N enregistrements peut être obtenue via des passes N-1 pour sélectionner et trier directement. L'algorithme spécifique est décrit comme suit:
État initial: la zone non ordonnée est R [1..N], et la zone ordonnée est vide;
Lorsque le i-thème commande (i = 1,2,3 ... n-1) commence, les zones commandées et non ordonnées actuelles sont respectivement R [1..i-1] et r (i..n). Cet ordre sélectionne l'enregistrement r [k] avec le plus petit mot-clé dans la zone actuelle non ordonnée, et l'échange avec le premier enregistrement R de la zone non ordonnée, de sorte que R [1..i] et r [i + 1..n) deviennent une nouvelle zone ordonnée avec une augmentation du nombre d'enregistrements et une nouvelle zone non ordonnée avec une diminution du nombre d'enregistrements;
Le voyage N-1 se termine et le tableau est commandé.
Implémentation du code JavaScript:
Fonction SELECTIONNTORT (Array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {var len = array.length, temp; pour (var i = 0; i <len - 1; i ++) {var min = array [i]; pour (var j = i + 1; j <len; j ++) {if (array [j] <min) {temp = min; min = array [j]; Array [j] = temp; }} Array [i] = min; } Return Array; } else {return 'array n'est pas un tableau!'; }}3) Analyse des algorithmes
Meilleur cas: t (n) = o (n2)
Pire des cas: t (n) = o (n2)
Moyenne: t (n) = o (n2)
4. tri à bulles
1) Introduction à l'algorithme
Le tri des bulles est un algorithme de tri simple. Il visite à plusieurs reprises les séquences à tri, compare deux éléments à la fois et les échange s'ils sont incorrects. Le travail de visite de la séquence est répété jusqu'à ce qu'aucun échange ne soit nécessaire, c'est-à-dire que la séquence a été triée. L'origine de cet algorithme est parce que plus l'élément "flottera lentement" vers le haut de la séquence via l'échange.
2) Description et implémentation de l'algorithme
L'algorithme spécifique est décrit comme suit:
Comparez les éléments adjacents. Si le premier est plus grand que le second, échangez-en deux;
Faites le même travail pour chaque paire d'éléments adjacents, du début de la première paire à la fin de la dernière paire, afin que le dernier élément soit le plus grand nombre;
Répétez les étapes ci-dessus pour tous les éléments sauf le dernier;
Répétez les étapes 1 à 3 jusqu'à ce que le tri soit terminé.
Implémentation du code JavaScript:
fonction bubblesort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {var len = array.length, temp; for (var i = 0; i <len - 1; i ++) {for (var j = len - 1; j> = i; j--) {if (array [j] <array [j - 1]) {temp = array [j]; Array [J] = Array [J - 1]; Array [J - 1] = temp; }}} Return Array; } else {return 'array n'est pas un tableau!'; }}3) Analyse des algorithmes
Meilleur cas: t (n) = o (n)
Pire des cas: t (n) = o (n2)
Moyenne: t (n) = o (n2)
5. Sort rapide
1) Introduction à l'algorithme
L'idée de base du tri rapide: divisez les enregistrements à tri en deux parties indépendantes à travers un ordre, et les mots clés de certains enregistrements sont plus petits que ceux de l'autre partie. Ensuite, les deux enregistrements peuvent être poursuivis à les trier séparément pour atteindre l'ordre de toute la séquence.
2) Description et implémentation de l'algorithme
Le tri rapide utilise la méthode de division pour diviser une chaîne en deux sous-listes. L'algorithme spécifique est décrit comme suit:
Choisir un élément de la séquence est appelé "principe" (pivot);
Réorganisez la séquence, 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 placé de chaque côté). Après cette partition, la référence est au milieu de la séquence. C'est ce qu'on appelle une opération de partition;
Trier récursivement les sous-séquences plus petites que l'élément de référence et les sous-séquences plus grandes que l'élément de référence.
Implémentation du code JavaScript:
// Méthode une fonction Quicksort (array, gauche, droite) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'Array' && typeof Left === 'Number' && typeof droite === '' Number ') {if (gauche <droite) {var x = array [droite], i = gauche - 1, temp; pour (var j = gauche; j <= droit; j ++) {if (array [j] <= x) {i ++; temp = array [i]; array [i] = array [j]; Array [j] = temp; }} Quicksort (Array, à gauche, i - 1); Quicksort (tableau, i + 1, à droite); }; } else {return 'Array n'est pas un tableau ou gauche ou droit n'est pas un nombre!'; }} var aaa = [3, 5, 2, 9, 1]; Quicksort (aaa, 0, aaa.length - 1); Console.log (AAA); // Méthode 2 var Quicksort = fonction (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var gauche = []; var droit = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {Left.push (arr [i]); } else {droite.push (arr [i]); }} return Quicksort (gauche) .Concat ([pivot], Quicksort (à droite)); };3) Analyse des algorithmes
Meilleur cas: t (n) = o (nlogn)
Pire des cas: t (n) = o (n2)
Moyenne: t (n) = o (nlogn)
6. tri de tas
1) Introduction à l'algorithme
Le tri du tas fait référence à un algorithme de tri conçu à l'aide de la structure des données du tas. L'empilement est une structure qui est approximativement entièrement binaire et satisfait les propriétés de l'empilement: c'est-à-dire que la valeur ou l'indice des clés d'un nœud enfant est toujours plus petit que (ou supérieur à) son nœud parent.
2) Description et implémentation de l'algorithme
L'algorithme spécifique est décrit comme suit:
La séquence initiale de mots clés à tri (R1, R2 ... RN) est construite en un grand tas supérieur, qui est la zone initiale non ordonnée;
L'échange de l'élément supérieur du tas r [1] avec le dernier élément r [n], et à l'heure actuelle, une nouvelle région non ordonnée (R1, R2, ... RN-1) et une nouvelle région ordonnée (RN) sont obtenues, et R [1,2 ... n-1] <= r [n] est satisfait;
Étant donné que le nouveau tas de tas R [1] après l'échange peut violer les propriétés du tas, il est nécessaire d'ajuster la zone actuelle non ordonnée (R1, R2, ... RN-1) au nouveau tas, puis d'échanger R [1] avec le dernier élément de la zone non ordonnée pour obtenir une nouvelle zone non ordonnée (R1, R2 ... RN-2) et une nouvelle zone ordonnée (RN-1, RN). Répétez ce processus jusqu'à ce que le nombre d'éléments dans la zone ordonnée soit N-1 et que l'ensemble du processus de tri soit terminé.
Implémentation du code JavaScript:
/ * Méthode Description: theap srie @param array array à tri * / function heapsort (array) {if (object.prototype.tostring.call (array) .slice (8, -1) === 'array') {// build heap var heapSize = array.length, temp; for (var i = math.floor (heapSize / 2); i> = 0; i--) {heapify (array, i, heapSize); } // Toi tas pour (var j = heapSize - 1; j> = 1; j--) {temp = array [0]; array [0] = array [j]; Array [j] = temp; taspify (array, 0, --hapsize); }} else {return 'array n'est pas un tableau!'; }} / * Méthode Description: Maintenez les propriétés de l'indice de tas @param arrAr @param x array indice @param len tas size * / function heapify (arr, x, len) {if (object.prototype.tostring.call (arr) .slice (8, -1) == 'array' && type x === '' numéro ') {var l = 2 * + 1, le plus grand = x, temp; if (l <len && arr [l]> arr [plus grand]) {plus grand = l; } if (r <len && arr [r]> arr [plus grand]) {le plus grand = r; } if (plus grand! = x) {temp = arr [x]; arr [x] = arr [plus grand]; arr [le plus grand] = temp; taspify (arr, grand, len); }} else {return 'arr n'est pas un tableau ou x n'est pas un nombre!'; }}3) Analyse des algorithmes
Meilleur cas: t (n) = o (nlogn)
Pire des cas: t (n) = o (nlogn)
Moyenne: t (n) = o (nlogn)
7. Commande
1) Introduction à l'algorithme
Le tri de fusion est un algorithme de tri efficace basé sur le fonctionnement de la fusion. Cet algorithme est une application très typique de la division et de la conquête. Le tri de fusion est une méthode de tri stable. Fusionner les sous-séquences ordonnées pour obtenir une séquence complètement ordonnée; Autrement dit, passez à chaque première commande de la sous-séquence, puis passez l'ordre des segments de la sous-séquence. Si deux tables ordonnées sont fusionnées dans une table ordonnée, elle est appelée fusion à 2 voies.
2) Description et implémentation de l'algorithme
L'algorithme spécifique est décrit comme suit:
Divisez la séquence d'entrée de la longueur n en deux sous-séquences de longueur n / 2;
Ces deux sous-séquences sont triées ensemble séparément;
Fusionner les deux sous-séquences triées dans une séquence triée finale.
Implémentation du code JavaScript:
fonction mergesort (array, p, r) {if (p <r) {var q = math.floor ((p + r) / 2); Mergesort (Array, P, Q); Mergesort (tableau, Q + 1, R); fusion (Array, P, Q, R); }} Fonction Merge (tableau, p, q, r) {var n1 = q - p + 1, n2 = r - q, gauche = [], droit = [], m = n = 0; for (var i = 0; i <n1; i ++) {Left [i] = array [p + i]; } pour (var j = 0; j <n2; j ++) {droit [j] = array [q + 1 + j]; } gauche [n1] = droit [n2] = nombre.max_value; pour (var k = p; k <= r; k ++) {if (gauche [m] <= droit [n]) {array [k] = gauche [m]; m ++; } else {array [k] = droit [n]; n ++; }}}3) Analyse des algorithmes
Meilleur cas: t (n) = o (n)
Pire des cas: t (n) = o (nlogn)
Moyenne: t (n) = o (nlogn)
8. Tri de seau
1) Introduction à l'algorithme
Le principe du tri du seau: en supposant que les données d'entrée sont uniformément distribuées, les données sont divisées en un nombre limité de seaux et chaque seau est trié séparément (il est possible d'utiliser d'autres algorithmes de tri ou de continuer à utiliser le tri de seau de manière récursive).
2) Description et implémentation de l'algorithme
L'algorithme spécifique est décrit comme suit:
Réglez un tableau quantitatif en tant que seau vide;
Itérer à travers les données d'entrée et mettre les données dans le seau correspondant une par une;
Triez chaque seau qui n'est pas vide;
Éplice les données triées d'un seau vide.
Implémentation du code JavaScript:
/ * Méthode Description: Bucket Sort @param array array @param num Number of Bucket * / function backetort (array, num) {if (array.length <= 1) {return array; } var len = array.length, Buckets = [], result = [], min = max = array [0], regex = '/ ^ [1-9] + [0-9] * $ /', espace, n = 0; num = num || ((num> 1 && regex.test (num))? num: 10); pour (var i = 1; i <len; i ++) {min = min <= array [i]? Min: Array [i]; max = max> = array [i]? Max: Array [i]; } spatial = (max - min + 1) / num; pour (var j = 0; j <len; j ++) {var index = math.floor ((array [j] - min) / space); if (Buckets [index]) {// Bucket non vide, insérez le tri var k = buckets [index] .length - 1; while (k> = 0 && buckets [index] [k]> array [j]) {buckets [index] [k + 1] = bucket [index] [k]; K--; } seaux [index] [k + 1] = array [j]; } else {// Bucket vide, initialisez les seaux [index] = []; seaux [index] .push (array [j]); }} while (n <num) {result = result.concat (buckets [n]); n ++; } Retour Résultat; }3) Analyse des algorithmes
Dans le meilleur des cas de tri du seau, le temps linéaire O (n), la complexité temporelle du tri du seau dépend de la complexité temporelle des données de tri entre les seaux, car la complexité temporelle des autres parties est O (n). De toute évidence, plus le seau est divisé, moins les données du seau sont les données, moins il faut de temps pour la trier. Mais la consommation d'espace correspondante augmentera.
9. Compter le tri
1) Introduction à l'algorithme
Le rythme de comptage est un algorithme de tri stable. Count Tri utilise un tableau supplémentaire C, où le i-th element est le nombre d'éléments avec une valeur égale à I dans le tableau A à tri. Ensuite, selon le tableau C, les éléments en A sont disposés à la bonne position. Il ne peut que trier les entiers.
2) Description et implémentation de l'algorithme
L'algorithme spécifique est décrit comme suit:
Trouvez les plus grands et les plus petits éléments du tableau à tri;
Comptez le nombre de fois chaque élément avec une valeur de I dans le tableau apparaît et le stockez dans le i-tème élément du tableau C;
Accumuler tous les comptes (à partir du premier élément de C, chaque élément et l'élément précédent sont ajoutés);
Remplissez le tableau cible de remplissage: placez chaque élément I dans l'élément C (i) th du nouveau tableau et soustriez C (i) par 1 pour chaque élément.
Implémentation du code JavaScript:
Fonction CountingSort (array) {var len = array.length, b = [], c = [], min = max = array [0]; pour (var i = 0; i <len; i ++) {min = min <= array [i]? Min: Array [i]; max = max> = array [i]? Max: Array [i]; C [Array [i]] = C [Array [i]]? C [Array [i]] + 1: 1; } pour (var j = min; j <max; j ++) {c [j + 1] = (c [j + 1] || 0) + (c [j] || 0); } pour (var k = len - 1; k> = 0; k--) {b [c [array [k]] - 1] = array [k]; C [Array [k]] -; } return b; }3) Analyse des algorithmes
Lorsque l'élément d'entrée est n entières entre 0 et K, son temps d'exécution est O (n + k). Le tri de compte n'est pas un tri de comparaison, et la vitesse de tri est plus rapide que n'importe quel algorithme de tri de comparaison. Étant donné que la longueur du tableau C utilisée pour compter dépend de la plage de données dans le tableau à tri (égal à la différence entre les valeurs maximales et minimales du tableau à tri plus 1), cela rend le tri, le tri nécessite beaucoup de temps et de mémoire pour les tableaux avec une grande plage de données.