Analyse graphique du code de l'implémentation JavaScript de l'algorithme de tri rapide-js tutoriel-php.cn

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

黄舟

Libérer： 2017-04-15 09:31:27

original

1650 Les gens l'ont consulté

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>

Copier après la connexion

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!