Comment implémenter un tri rapide en utilisant js

Le tri rapide, qui est également l'algorithme de tri le plus utilisé en pratique, est rapide et efficace. Tout comme son nom, le tri rapide est le meilleur algorithme de tri.

1) Principe de l'algorithme

L'idée de base du tri rapide : le tri en un seul passage Séparez les enregistrements à trier en deux parties indépendantes. Les mots-clés d'une partie de l'enregistrement sont plus petits que les mots-clés de l'autre partie. Vous pouvez ensuite continuer à trier les deux parties des enregistrements séparément pour obtenir l'ordre des. toute la séquence.

2) Description de l'algorithme

Le tri rapide utilise la méthode diviser pour régner pour diviser une chaîne (liste) en deux sous-listes. L'algorithme spécifique est décrit comme suit :

<1> Choisissez un élément de la séquence, appelé « pivot » ; ;2> Réorganisez le tableau de sorte que tous les éléments plus petits que la valeur de base soient placés devant la base et que tous les éléments plus grands que la valeur de base soient placés derrière la base (le même nombre peut être placé de chaque côté). Une fois cette partition terminée, la base se trouve au milieu de la séquence. C'est ce qu'on appelle une opération de partition ;

<3> Trier de manière récursive le sous-tableau d'éléments plus petit que la valeur de base et le sous-tableau d'éléments supérieur à la valeur de base.

3) Implémentation du code JavaScript

4) Analyse d'algorithme

function paritition(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}
function quickSort(arr, low, high) {
  if (low < high) {
    let pivot = paritition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
  }
  return arr;
}
  var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52];    
  console.log(quickSort(arr,0,arr.length-1));

Meilleur cas : T(n) = O(nlogn)

Pire cas : T (n) = O(n^2)

Cas moyen : T(n) = O(nlogn)

Liste des dix meilleurs algorithmes :

1.

Utilisez JavaScript pour implémenter les dix principaux algorithmes de tri classiques-tri à bulles

2.

Utilisez JavaScript pour implémenter les dix principaux algorithmes de tri classiques-tri par sélection

3.Utilisez JavaScript pour implémenter Top dix des algorithmes de tri classiques - Tri par insertion

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!