Maison >interface Web >js tutoriel >Analyse graphique du code de l'implémentation JavaScript de l'algorithme de tri rapide

Analyse graphique du code de l'implémentation JavaScript de l'algorithme de tri rapide

黄舟original: 2017-04-15 09:31:271651parcourir

Cet article présente principalement l'algorithme de tri rapide basé sur JavaScript. Il analyse le principe du tri rapide et fournit les étapes de fonctionnement et les techniques de mise en œuvre associées du tri rapide javascript sous forme d'exemples. it Vous pouvez vous référer à ce qui suit

L'exemple de cet article décrit l'algorithme de tri rapide basé sur JavaScript. Partagez-le avec tout le monde pour votre référence. Les détails sont les suivants :

Tout d'abord, permettez-moi de vous présenter le le tri des bulles. . Tout d'abord, mettez la clé d'un enregistrement avec la clé du deuxième enregistrement. Si l'ordre est inversé, les deux clés sont échangées, puis la deuxième et la troisième sont comparées jusqu'à ce que la dernière comparaison soit terminée. Il s'agit du premier bouillonnement, et du coup, l'enregistrement avec le mot-clé le plus gros est placé en dernière position. Bullez ensuite les n-1 premiers éléments de la séquence pour la deuxième fois et sélectionnez l'avant-dernier. Et ainsi de suite jusqu'à ce que tous soient sélectionnés, et que le bouillonnement se termine .

Grâce à l'analyse, on peut conclure que la complexité temporelle du tri à bulles est O(n2).

Le tri rapide est une amélioration du tri à bulles, c'est l'un des tris les plus rapides pour gérer de grands ensembles de données, via la méthode récursion pour décomposez séquentiellement les données en différentes sous-séquences contenant des éléments plus petits et des éléments plus grands, et répétez le processus jusqu'à ce que toutes les données soient ordonnées. Cet algorithme doit d'abord sélectionner une valeur de base et procéder autour de la valeur de base.

Un exemple est le suivant :

L'idée de l'algorithme est la suivante :

Sélectionner un élément de base et ajoutez la liste Divisez en deux sous-séquences

Réorganisez la liste en plaçant tous les éléments plus petits que l'élément de référence à l'avant et les plus grands à l'arrière

Répétez les deux étapes ci-dessus pour la sous-séquence des éléments plus petits et la sous-séquence des éléments plus grands.

Nous implémentons le code via js comme suit :

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>JavaScript快速排序</title>
</head>
<body>
<script type="text/javascript">
  function qSort(nums) {//快速排序
    if(nums.length==0){
      return [];
    }
    var lesser=[];
    var greater=[];
    var pivot=nums[0];//选择基准元素
    for(var i=1;i<nums.length;i++){
      if(nums[i]<pivot){//分成两个之序列
        lesser.push(nums[i]);
      }else{
        greater.push(nums[i]);
      }
    }
    return qSort(lesser).concat(pivot,qSort(greater));//递归
  }
  function show(nums){//显示数组
    for(var i=0;i<nums.length;i++){
      document.write(nums[i]+&#39; &#39;);
    }
    document.write(&#39;<br>&#39;);
  }
  var nums=[68,80,12,80,95,70,79,27,88,93];
  show(nums);//newNums
  var newNums=qSort(nums);//希尔排序
  show(newNums);//0 0 2 3 4 5 5 6 8 9
</script>
</body>
</html>

En termes de temps moyen, tri rapide est actuellement considérée comme la meilleure méthode de tri interne. Le tri rapide est très adapté aux grands ensembles de données, mais les performances diminueront lors du traitement de petits ensembles de données. Sa complexité temporelle est O(nlog2n)

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!

Déclaration：

Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Article précédent：Exemple d'analyse de l'implémentation JavaScript de l'algorithme de tri par sélection (image)Article suivant：Exemple d'analyse de l'implémentation JavaScript de l'algorithme de tri par sélection (image)

Articles Liés

Voir plus