JS implémente le tri par fusion

Cet article présente principalement l'implémentation JS du tri par fusion, qui a une certaine valeur de référence. Maintenant, je le partage avec tout le monde. Les amis dans le besoin peuvent s'y référer

Analyse de la pile de mémoire récursive

. Je n'ai jamais compris la récursivité en profondeur. La raison en est que le processus récursif est très abstrait et je ne peux pas analyser clairement le processus de retour de la pile mémoire. De temps en temps, je suis tombé sur un article de blog sur la récursivité via Google (je dois dire que les problèmes techniques nécessitent encore plus de Google), et j'ai soudain compris l'analyse de la pile mémoire du processus récursif. Le processus d'analyse est répertorié ci-dessous :

<.>

// A C++ program to demonstrate working of recursion
#include<bits>
using namespace std;
void printFun(int test)
{
    if (test L'image ci-dessous est exacte. L'ensemble du processus récursif est répertorié. Si vous rencontrez un seul problème de récursion à l'avenir, vous pouvez utiliser cette méthode pour l'analyser (pour plusieurs récursions, essayez de dessiner les deux récursions dans la fusion). trier, mais il n'y a vraiment aucun moyen de le taper proprement, alors j'ai abandonné ) <p></p>
<p><img src="https://img.php.cn//upload/image/198/863/317/1530956481159780.jpg" title="1530956481159780.jpg" alt="JS implémente le tri par fusion"></p> Revenons au fait, analysons le tri par fusion. <p></p>Tri par fusion<h3></h3>Le tri par fusion adopte l'idée de diviser pour régner. Le premier est "diviser", qui divise à plusieurs reprises un tableau en deux petits tableaux jusqu'à ce que chaque tableau n'en ait qu'un. élément ; deuxièmement, il "guérit", en commençant par le plus petit tableau, en fusionnant les deux par ordre de taille, jusqu'à ce que l'union ait la taille du tableau d'origine, voici le diagramme : <p></p>
<p><img src="https://img.php.cn//upload/image/223/850/313/1530956488945859.png" title="1530956488945859.png" alt="JS implémente le tri par fusion"></p>Observez le processus de "durcissement", on peut voir que "durcir" signifie en fait fusionner des tableaux déjà ordonnés en un tableau ordonné plus grand. Alors, comment fusionner des tableaux déjà triés dans un tableau trié plus grand ? C'est très simple. Créez un tableau temporaire C, comparez A[0], B[0], mettez la plus petite valeur dans C[0], puis comparez A[1] et B[0] (ou A[0], B [1]), mettez la plus petite valeur dans C[1] jusqu'à ce que A et B aient été parcourus. On peut voir que les tableaux A et B ne doivent être parcourus qu'une seule fois, donc la complexité temporelle du tri de deux tableaux ordonnés est O(n). <p></p>Et « diviser » signifie diviser le tableau d'origine en deux parties l'une après l'autre jusqu'à ce qu'il ne reste plus qu'un seul élément dans chaque tableau. Le tableau à un élément est naturellement en ordre, de sorte que le processus de « durcissement » peut commencer. <p></p> Analyse de complexité temporelle : le processus de division nécessite trois étapes : log8 = 3, et chaque étape doit parcourir 8 éléments une fois, donc un total de 8 log8) instructions doivent être exécutées pour 8 éléments, puis pour n elements , la complexité temporelle est O(nlogn). <p></p>Le code utilise deux récursions, ce qui est très abstrait et difficile à comprendre. Il m'a fallu une page entière de diagrammes d'appels de pile pour le comprendre (c'est trop compliqué donc je ne le publierai pas). essayez-le. <p></p>
<pre class="brush:php;toolbar:false">// 融合两个有序数组，这里实际上是将数组 arr 分为两个数组
function mergeArray(arr, first, mid, last, temp) {
  let i = first; 
  let m = mid;
  let j = mid+1;
  let n = last;
  let k = 0;
  while(iCe qui précède représente l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'étude de chacun. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois ! <p></p>Recommandations associées : <p></p><p>Implémentation JS du tri Hill<a title="JS实现希尔排序" href="http://www.php.cn/js-tutorial-406221.html" target="_blank"></a><br></p><p>Jquery ajoute un masque de transition de chargement<a title="Jquery添加loading过渡遮罩" href="http://www.php.cn/js-tutorial-406220.html" target="_blank"></a> <br></p>

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!