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

資訊專(zhuān)欄INFORMATION COLUMN

js 歸并算法

jimhs / 808人閱讀

摘要：正常模式下，函數(shù)內(nèi)部有兩個(gè)變量，可以跟蹤函數(shù)的調(diào)用棧。尾調(diào)用優(yōu)化發(fā)生時(shí)，函數(shù)的調(diào)用棧會(huì)改寫(xiě)，因此上面兩個(gè)變量就會(huì)失真。

作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法：

1.自上而下的遞歸（所有遞歸的方法都可以用迭代重寫(xiě)，所以就有了第2種方法）
2.自下而上的迭代

這里使用尾遞歸調(diào)用
ES6的尾遞歸優(yōu)化只在嚴(yán)格模式下才會(huì)開(kāi)啟。
正常模式下，函數(shù)內(nèi)部有兩個(gè)變量，可以跟蹤函數(shù)的調(diào)用棧。
func.arguments：返回調(diào)用時(shí)函數(shù)的參數(shù)。
func.caller：返回調(diào)用當(dāng)前函數(shù)的那個(gè)函數(shù)。
尾調(diào)用優(yōu)化發(fā)生時(shí)，函數(shù)的調(diào)用棧會(huì)改寫(xiě)，因此上面兩個(gè)變量就會(huì)失真。嚴(yán)格模式禁用這兩個(gè)變量，所以尾調(diào)用模式僅在嚴(yán)格模式下生效。
始終都是O(n log n）的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間

function mergeSort(arr) {

let len = arr.length;
if (len < 2) {
    return arr;
}

let middle = Math.floor(len/2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));

}

function merge(left, right) {

let result = [];

while (left.length && right.length) {
    if (left[0] <= right[0]) {
        result.push(left.shift());
    } else {
        result.push(right.shift());
    }
}

while (left.length) {
    result.push(left.shift());
}
while (right.length) {
    result.push(right.shift());
}
return result

}

const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(mergeSort(arr));

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

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

相關(guān)文章

  • js歸并排序算法的原理及簡(jiǎn)單demo

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

    TigerChain 評(píng)論0 收藏0

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

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

    stormjun 評(píng)論0 收藏0

  • JS數(shù)據(jù)結(jié)構(gòu)與算法_排序和搜索算法

    摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法樹(shù)寫(xiě)在前面這是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的最后一篇博客，也是在面試中常常會(huì)被問(wèn)到的一部分內(nèi)容排序和搜索。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_樹(shù) 寫(xiě)在前面 這是《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》的最后一篇博客，也是在面試中常常會(huì)被問(wèn)到的一部分內(nèi)容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類(lèi)似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無(wú)心去深入研究排序相...

    姘擱『 評(píng)論0 收藏0

  • JS排序算法

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

    notebin 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

jimhs

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<