成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

bluesky / 2379人閱讀

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

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

一直對遞歸理解不深，原因是遞歸的過程很抽象，分析不清內(nèi)存堆棧的返回過程。偶然google到一篇博文遞歸(不得不說，技術(shù)問題還是要多google)，對遞歸過程的內(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);
}

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

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

歸并排序

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

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

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

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

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

// 融合兩個有序數(shù)組，這里實際上是將數(shù)組 arr 分為兩個數(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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/95947.html

相關(guān)文章

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

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

    TigerChain 評論0 收藏0

  • ts/js歸并排序實現(xiàn)（穩(wěn)定排序）

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

    vvpvvp 評論0 收藏0

  • js算法-歸并排序（merge_sort）

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

    stormjun 評論0 收藏0

  • JS排序算法

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

    notebin 評論0 收藏0

  • JS排序算法

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

    sihai 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<