JS實(shí)現(xiàn)歸并排序

bluesky 發(fā)布于2019-08-22 18:31 / 2371人閱讀

摘要：言歸正傳，下面分析歸并排序。融合兩個(gè)有序數(shù)組，這里實(shí)際上是將數(shù)組分為兩個(gè)數(shù)組遞歸實(shí)現(xiàn)歸并排序左子數(shù)組有序右子數(shù)組有序

遞歸的內(nèi)存堆棧分析

一直對(duì)遞歸理解不深，原因是遞歸的過程很抽象，分析不清內(nèi)存堆棧的返回過程。偶然google到一篇博文遞歸(不得不說，技術(shù)問題還是要多google)，對(duì)遞歸過程的內(nèi)存堆棧分析豁然開朗，下面先列出分析過程：

// A C++ program to demonstrate working of recursion
#include
using namespace std;
void printFun(int test)
{
    if (test < 1)
        return;
    else
    {
        cout << test << " ";
        printFun(test-1);    // statement 2
        cout << test << " ";
        return;
    }
}
int main()
{
    int test = 3;
    printFun(test);
}

下面這個(gè)圖準(zhǔn)確的列出了整個(gè)遞歸的過程，以后遇到單次遞歸問題，完全可以用此方法分析（對(duì)于多次遞歸情況，嘗試畫了一下歸并排序里的兩次遞歸，實(shí)在沒有辦法整潔的排版，作罷。。）

言歸正傳，下面分析歸并排序。

歸并排序

歸并排序采用的是分治的思想，首先是“分”，將一個(gè)數(shù)組反復(fù)二分為兩個(gè)小數(shù)組，直到每個(gè)數(shù)組只有一個(gè)元素；其次是“治”，從最小數(shù)組開始，兩兩按大小順序合并，直到并為原始數(shù)組大小，下面是圖解：

觀察下“治”的過程，可以看出，“治”實(shí)際上是將已經(jīng)有序的數(shù)組合并為更大的有序數(shù)組。那么怎樣將已經(jīng)有序的數(shù)組合并為更大的有序數(shù)組？很簡(jiǎn)單，創(chuàng)建一個(gè)臨時(shí)數(shù)組C，比較A[0]，B[0]，將較小值放到C[0]，再比較A[1]與B[0]（或者A[0]，B[1]），將較小值放到C[1]，直到對(duì)A，B都遍歷一遍。可以看出數(shù)組A，B都只需遍歷一遍，所以對(duì)兩個(gè)有序數(shù)組的排序的時(shí)間復(fù)雜度為O(n)。

而“分”就是將原始數(shù)組逐次二分，直到每個(gè)數(shù)組只剩一個(gè)元素，一個(gè)元素的數(shù)組自然是有序的，所以就可以開始“治”的過程了。

時(shí)間復(fù)雜度分析：分的過程需要三步：log8 = 3，而每一步都需要遍歷一次8個(gè)元素，所以8個(gè)元素共需要運(yùn)行 8log8 次指令，那么對(duì)于 n 個(gè)元素，時(shí)間復(fù)雜度為 O(nlogn)。

代碼中運(yùn)用了兩次遞歸，十分抽象難懂，畫了一整頁堆棧調(diào)用圖，才弄明白（太凌亂就不貼了），大家可以試試。

// 融合兩個(gè)有序數(shù)組，這里實(shí)際上是將數(shù)組 arr 分為兩個(gè)數(shù)組
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<=m && j<=n) {
    if(arr[i] < arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }
  while(i<=m) {
    temp[k++] = arr[i++];
  }
  while(j<=n) {
    temp[k++] = arr[j++];
  } 
  for(let l=0; l