JS實現歸并排序

bluesky 發布于2019-08-22 18:31 / 2377人閱讀

摘要：言歸正傳，下面分析歸并排序。融合兩個有序數組，這里實際上是將數組分為兩個數組遞歸實現歸并排序左子數組有序右子數組有序

遞歸的內存堆棧分析

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

// 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);
}

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

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

歸并排序

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

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

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

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

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

// 融合兩個有序數組，這里實際上是將數組 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<=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

云服務器 GPU云服務器 js 歸并排序歸并排序二路歸并排序歸并排序算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/95947.html

js歸并排序算法的原理及簡單demo

摘要：最近看了一道如何給阿里兩萬多名員工按照年齡排序的面試題后，很想記錄下來自己的解題思路，下面綜合考慮到基數較大和穩定性，我們采取歸并排序的算法歸并算法分為兩個兩個靈魂步驟，即拆分歸并我們先把兩萬多名員工的基數縮小至六名員工的基數，他們的年齡數最近看了一道如何給阿里兩萬多名員工按照年齡排序的面試題后，很想記錄下來自己的解題思路，下面：綜合考慮到基數較大和穩定性，我們采取歸并排序的算法；歸...

TigerChain 2019-08-23 17:16 評論0 收藏0
ts/js歸并排序實現（穩定排序）

摘要：穩定排序穩定排序是指，如果原數組中有多個元素是相等的，那么這些元素在排序后數組的相對順序應該保持不變。實現歸并排序穩定排序。的參數必須為數組排序范圍順序已經正確歸并排序穩定排序。穩定排序穩定排序是指，如果原數組中有多個元素是相等的，那么這些元素在排序后數組的相對順序應該保持不變。比如：我們對{name:string, age:number}[]數組用age進行排序，有很多人是25歲...

vvpvvp 2019-08-22 16:30 評論0 收藏0
js算法-歸并排序（merge_sort）

摘要：歸并排序是建立在歸并操作上的一種有效的排序算法該算法是采用分治法的一個非常典型的應用。若將兩個有序表合并成一個有序表，稱為二路歸并。歸并排序歸并排序是一種非常穩定的排序方法，它的時間復雜度無論是平均，最好，最壞都是。歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個非常典型的應用。將已有序的子序列合并...

stormjun 2019-08-23 14:37 評論0 收藏0
JS排序算法

摘要：冒泡排序冒泡算法是比較相鄰的兩項，如果前者比后者大，就交換他們。插入排序最好情況下時間復雜度是，其他情況下也都是。代碼演示插入排序歸并排序原生里面的方法，在里面是用歸并排序實現的，而在里面是用快速排序的變體來實現的。 1、冒泡排序冒泡算法是比較相鄰的兩項，如果前者比后者大，就交換他們。假設一共有n項，那么一共需要n-1趟，第一趟需要交換n-1次，但是第一趟結束后，最后一項基本確定就...

notebin 2019-08-01 15:39 評論0 收藏0
JS排序算法

摘要：冒泡排序冒泡算法是比較相鄰的兩項，如果前者比后者大，就交換他們。插入排序最好情況下時間復雜度是，其他情況下也都是。代碼演示插入排序歸并排序原生里面的方法，在里面是用歸并排序實現的，而在里面是用快速排序的變體來實現的。 1、冒泡排序冒泡算法是比較相鄰的兩項，如果前者比后者大，就交換他們。假設一共有n項，那么一共需要n-1趟，第一趟需要交換n-1次，但是第一趟結束后，最后一項基本確定就...

sihai 2019-08-20 10:37 評論0 收藏0