JS implementiert die Zusammenführungssortierung

Dieser Artikel stellt hauptsächlich die JS-Implementierung der Zusammenführungssortierung vor, die einen gewissen Referenzwert hat. Jetzt kann ich sie mit allen teilen, die sie brauchen.

Rekursive Speicherstapelanalyse

Ich habe die Rekursion nie wirklich verstanden. Der Grund dafür ist, dass der rekursive Prozess sehr abstrakt ist und ich den Rückgabeprozess des Speicherstapels nicht klar analysieren kann. Ich habe versehentlich einen Blog-Beitrag zum Thema Rekursion gegoogelt (ich muss sagen, dass technische Probleme immer noch mehr Google erfordern) und bin plötzlich auf die Speicherstapelanalyse des rekursiven Prozesses aufmerksam geworden. Der Analyseprozess ist unten aufgeführt:

// A C++ program to demonstrate working of recursion
#include<bits>
using namespace std;
void printFun(int test)
{
    if (test <p>Die folgende Abbildung ist korrekt. Wenn Sie in Zukunft auf ein einzelnes Rekursionsproblem stoßen, können Sie es mit dieser Methode analysieren (versuchen Sie bei mehreren Rekursionen, die beiden Rekursionen in der Zusammenführungssortierung zu zeichnen, aber dort). ist wirklich keine Möglichkeit, es sauber zu tippen, also geben Sie auf)</p>
<p><img src="/static/imghw/default1.png" data-src="https://img.php.cn//upload/image/198/863/317/1530956481159780.jpg" class="lazy" title="1530956481159780.jpg" alt="JS implementiert die Zusammenführungssortierung"></p>
<p>Um zum Punkt zurückzukommen, lassen Sie uns die Zusammenführungssortierung analysieren. </p>
<h3 id="Merge-Sortierung">Merge-Sortierung</h3>
<p>Merge-Sortierung übernimmt die Idee des Teilens und Eroberns. Das erste ist „Teilen“, das ein Array wiederholt in zwei kleine Arrays teilt, bis jedes Array nur noch eines hat Element; zweitens wird es „ausgehärtet“, ausgehend vom kleinsten Array, wobei die beiden in der Reihenfolge ihrer Größe zusammengeführt werden, bis die Vereinigung die Größe des ursprünglichen Arrays erreicht. Das folgende Diagramm ist: </p>
<p><img src="/static/imghw/default1.png" data-src="https://img.php.cn//upload/image/223/850/313/1530956488945859.png" class="lazy" title="1530956488945859.png" alt="JS implementiert die Zusammenführungssortierung"></p>
<p>Beobachten Sie den Prozess des „Aushärtens“. Es ist ersichtlich, dass „Aushärten“ tatsächlich das Zusammenführen bereits geordneter Arrays zu einem größeren geordneten Array bedeutet. Wie kann man also bereits sortierte Arrays zu einem größeren sortierten Array zusammenführen? Es ist ganz einfach. Erstellen Sie ein temporäres Array C, vergleichen Sie A[0], B[0], geben Sie den kleineren Wert in C[0] ein und vergleichen Sie dann A[1] und B[0] (oder A[0], B [1]), geben Sie den kleineren Wert in C[1] ein, bis sowohl A als auch B durchlaufen wurden. Es ist ersichtlich, dass die Arrays A und B nur einmal durchlaufen werden müssen, sodass die zeitliche Komplexität der Sortierung zweier geordneter Arrays O(n) beträgt. </p>
<p>Und „Teilen“ bedeutet, das ursprüngliche Array nacheinander in zwei Teile zu teilen, bis jedes Array nur noch ein Element enthält. Das Ein-Element-Array ist natürlich in Ordnung, sodass der Prozess des „Aushärtens“ beginnen kann. </p>
<p> Zeitkomplexitätsanalyse: Der Divisionsprozess erfordert drei Schritte: log8 = 3, und jeder Schritt muss 8 Elemente einmal durchlaufen, sodass insgesamt 8 log8)-Anweisungen für 8 Elemente und dann für n ausgeführt werden müssen Elemente, die Zeitkomplexität beträgt O(nlogn). </p>
<p>Der Code verwendet zwei Rekursionen, was sehr abstrakt und schwer zu verstehen ist. Ich habe eine ganze Seite Stapelaufrufdiagramme gebraucht, um es herauszufinden (es ist zu chaotisch, deshalb werde ich es nicht veröffentlichen). Probieren Sie es aus. </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(i<p>Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, er wird für das Studium aller hilfreich sein. Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website. </p><p>Verwandte Empfehlungen: </p><p><a title="JS实现希尔排序" href="http://www.php.cn/js-tutorial-406221.html" target="_blank">JS-Implementierung der Hill-Sortierung</a><br></p><p><a title="Jquery添加loading过渡遮罩" href="http://www.php.cn/js-tutorial-406220.html" target="_blank">Jquery fügt Ladeübergangsmaske hinzu</a><br> </p>

Das obige ist der detaillierte Inhalt vonJS implementiert die Zusammenführungssortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!