首頁  >  文章  >  web前端  >  JS實作歸併排序

JS實作歸併排序

不言
不言原創
2018-07-07 17:42:062170瀏覽

這篇文章主要介紹了關於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="https://img.php.cn//upload/image/198/863/317/1530956481159780.jpg" title="1530956481159780.jpg" alt="JS實作歸併排序"></p>
<p>言歸正傳,下面分析歸併排序。 </p>
<h3>歸併排序</h3>
<p>歸併排序採用的是分治的思想,首先是“分”,將一個數組反覆二分為兩個小數組,直到每個數組只有一個元素;其次是“治”,從最小數組開始,兩兩按大小順序合併,直到並為原始數組大小,下面是圖解:</p>
<p><img src="https://img.php.cn//upload/image/223/850/313/1530956488945859.png" 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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn