js 歸并算法

jimhs 發布于2019-08-23 14:55 / 806人閱讀

摘要：正常模式下，函數內部有兩個變量，可以跟蹤函數的調用棧。尾調用優化發生時，函數的調用棧會改寫，因此上面兩個變量就會失真。

作為一種典型的分而治之思想的算法應用，歸并排序的實現由兩種方法：

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

這里使用尾遞歸調用
ES6的尾遞歸優化只在嚴格模式下才會開啟。
正常模式下，函數內部有兩個變量，可以跟蹤函數的調用棧。
func.arguments：返回調用時函數的參數。
func.caller：返回調用當前函數的那個函數。
尾調用優化發生時，函數的調用棧會改寫，因此上面兩個變量就會失真。嚴格模式禁用這兩個變量，所以尾調用模式僅在嚴格模式下生效。
始終都是O(n log n）的時間復雜度。代價是需要額外的內存空間

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

GPU云服務器云服務器歸并算法歸并排序算法 python歸并算法用c語言寫歸并算法

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

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

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

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

TigerChain 2019-08-23 17:16 評論0 收藏0
js算法-歸并排序（merge_sort）

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

stormjun 2019-08-23 14:37 評論0 收藏0
JS數據結構與算法_排序和搜索算法

摘要：上一篇數據結構與算法樹寫在前面這是學習數據結構與算法的最后一篇博客，也是在面試中常常會被問到的一部分內容排序和搜索。上一篇：JS數據結構與算法_樹寫在前面這是《學習JavaScript數據結構與算法》的最后一篇博客，也是在面試中常常會被問到的一部分內容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無心去深入研究排序相...

姘擱『 2019-08-23 16:26 評論0 收藏0
JS排序算法

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

notebin 2019-08-01 15:39 評論0 收藏0