JS實作歸併排序

這篇文章主要介紹了關於JS實作歸併排序，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

#遞歸的記憶體堆疊分析

一直對遞歸理解不深，原因是遞歸的過程很抽象，分析不清記憶體堆疊的回傳過程。偶然google到一篇博文遞歸(不得不說，技術問題還是要多google)，對遞歸過程的內存堆疊分析豁然開朗，下面先列出分析過程：

// A C++ program to demonstrate working of recursion
#include<bits>
using namespace std;
void printFun(int test)
{
    if (test <p>下面這個圖準確的列出了整個遞歸的過程，以後遇到單次遞歸問題，完全可以用此方法分析（對於多次遞歸情況，嘗試畫了一下歸併排序裡的兩次遞歸，實在沒有辦法整潔的排版，作罷。。 ）</p>
<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn//upload/image/198/863/317/1530956481159780.jpg?x-oss-process=image/resize,p_40" class="lazy" title="1530956481159780.jpg" alt="JS實作歸併排序"></p>
<p>言歸正傳，下面分析歸併排序。 </p>
<h3 id="歸併排序">歸併排序</h3>
<p>歸併排序採用的是分治的思想，首先是“分”，將一個數組反覆二分為兩個小數組，直到每個數組只有一個元素；其次是“治”，從最小數組開始，兩兩按大小順序合併，直到並為原始數組大小，下面是圖解：</p>
<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn//upload/image/223/850/313/1530956488945859.png?x-oss-process=image/resize,p_40" class="lazy" title="1530956488945859.png" alt="JS實作歸併排序"></p>##觀察下“治”的過程，可以看出，「治」實際上是將已經有序的數組合併為更大的有序數組。那麼怎樣將已經有序的數組合併為更大的有序數組？很簡單，建立一個臨時數組C，比較A[0]，B[0]，將較小值放到C[0]，再比較A[1]與B[0]（或A[0]，B [1]），將較小值放到C[1]，直到對A，B都遍歷一遍。可以看出數組A，B都只需要遍歷一遍，所以兩個有序數組的排序的時間複雜度為O(n)。 <p></p>而「分」就是將原始數組逐次二分，直到每個數組只剩下一個元素，一個元素的數組自然是有序的，所以就可以開始「治」的過程了。 <p></p>時間複雜度分析：分的過程需要三個步驟：log8 = 3，而每一步都需要遍歷一次8個元素，所以8個元素共需要執行8log8)次指令，那麼對於n 個元素，時間複雜度為O(nlogn)。 <p></p>程式碼中運用了兩次遞歸，十分抽象難懂，畫了一整頁堆疊呼叫圖，才弄清楚（太凌亂就不貼了），大家可以試試看。 <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(i以上就是本文的全部內容，希望對大家的學習有所幫助，更多相關內容請關注PHP中文網！ <p></p>相關推薦：<p></p><p>JS實作希爾排序<a title="JS实现希尔排序" href="http://www.php.cn/js-tutorial-406221.html" target="_blank"></a><br></p><p>Jquery新增loading過渡遮罩<a title="Jquery添加loading过渡遮罩" href="http://www.php.cn/js-tutorial-406220.html" target="_blank"></a> <br></p>

以上是JS實作歸併排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！