Exemples pour expliquer plusieurs algorithmes de tri couramment utilisés en JavaScript

JavaScript est un langage de programmation populaire utilisé pour créer de l'interactivité sur les pages Web. Le tri est l'un des algorithmes importants en informatique, et le tri en JavaScript est également une compétence qui doit être maîtrisée. Dans cet article, nous présenterons plusieurs algorithmes de tri couramment utilisés en JavaScript et comment les implémenter.

1. Bubble Sort

Le tri à bulles est un algorithme de tri simple et intuitif. Son idée de base est de comparer à chaque fois deux éléments adjacents, et si leur ordre est incorrect, d'échanger leurs positions. Après chaque tour de tri, le plus grand élément est déplacé vers la fin du tableau. Ce processus est répété jusqu'à ce que l'ensemble du tableau soit trié.

Ce qui suit est l'implémentation JavaScript du tri à bulles :

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

Dans le code ci-dessus, nous utilisons des boucles imbriquées pour comparer les éléments adjacents dans l'ordre, et si l'élément actuel est supérieur à l'élément suivant, échangeons leurs positions. À chaque itération de la boucle, le plus grand élément est déplacé vers la fin du tableau. La complexité temporelle de cet algorithme est O(n^2).

2. Tri par sélection

Le tri par sélection est un autre algorithme de tri simple. Son idée de base est de sélectionner à chaque fois le plus petit élément du tableau et de le placer à la fin du tableau trié. La complexité temporelle du tri par sélection est également O(n^2).

Voici l'implémentation JavaScript du tri par sélection :

function selectionSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    var minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      var temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

Dans le code ci-dessus, nous utilisons deux boucles imbriquées pour trouver la valeur minimale et l'échangeons à la fin du tableau trié.

3. Tri par insertion

Le tri par insertion est un algorithme de tri simple mais efficace. Son idée de base est d'insérer un élément à trier dans une séquence déjà triée. Pour une séquence non ordonnée, nous partons toujours du premier élément, retirons un élément de gauche à droite, puis l'insérons à la position appropriée de la séquence ordonnée. Jusqu'à ce que tous les éléments soient récupérés, le processus de tri est terminé.

Ce qui suit est l'implémentation JavaScript du tri par insertion :

function insertionSort(arr) {
  var len = arr.length;
  var current, j;
  for (var i = 1; i < len; i++) {
    current = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

Dans le code ci-dessus, nous utilisons une boucle while pour déplacer les éléments triés vers la droite afin de laisser de la place à l'insertion de nouveaux éléments. La complexité temporelle de cet algorithme est O(n^2).

4. Tri rapide

Le tri rapide est un algorithme de tri couramment utilisé et efficace. L'idée de base est de choisir un numéro de base et de comparer tous les nombres de la séquence avec ce numéro de base. Placez les nombres plus petits que le numéro de base à gauche du numéro de base et les nombres plus grands que le numéro de base à droite du numéro de base, puis traitez de manière récursive les sous-séquences gauche et droite.

Ce qui suit est l'implémentation JavaScript du tri rapide :

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

Dans le code ci-dessus, nous sélectionnons d'abord un numéro de référence, puis parcourons toute la séquence, mettons les nombres plus petits que le numéro de référence dans un tableau et mettons les nombres plus grands. que le numéro de référence dans un tableau dans un autre tableau. Enfin, nous traitons de manière récursive les tableaux gauche et droit et les fusionnons avec le numéro de base. La complexité temporelle de cet algorithme est O(nlogn).

Résumé

Cet article présente plusieurs algorithmes de tri courants et comment ils sont implémentés en JavaScript. Qu'il s'agisse du tri à bulles, du tri par sélection ou du tri par insertion, ce sont tous des algorithmes de tri très basiques et faciles à comprendre, adaptés aux débutants pour apprendre et comprendre. Si vous avez une étude plus approfondie et complète des algorithmes de tri, vous pouvez également essayer d'utiliser certains algorithmes de tri avancés, tels que le tri par fusion, le tri par tas, etc.

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!