資訊專欄INFORMATION COLUMN
摘要：正常模式下，函數(shù)內(nèi)部有兩個變量，可以跟蹤函數(shù)的調(diào)用棧。尾調(diào)用優(yōu)化發(fā)生時，函數(shù)的調(diào)用棧會改寫，因此上面兩個變量就會失真。
作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實現(xiàn)由兩種方法：
1.自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第2種方法）
2.自下而上的迭代
這里使用尾遞歸調(diào)用
ES6的尾遞歸優(yōu)化只在嚴(yán)格模式下才會開啟。
正常模式下，函數(shù)內(nèi)部有兩個變量，可以跟蹤函數(shù)的調(diào)用棧。
func.arguments：返回調(diào)用時函數(shù)的參數(shù)。
func.caller：返回調(diào)用當(dāng)前函數(shù)的那個函數(shù)。
尾調(diào)用優(yōu)化發(fā)生時，函數(shù)的調(diào)用棧會改寫，因此上面兩個變量就會失真。嚴(yán)格模式禁用這兩個變量，所以尾調(diào)用模式僅在嚴(yán)格模式下生效。
始終都是O(n log n）的時間復(fù)雜度。代價是需要額外的內(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/101341.html
摘要：最近看了一道如何給阿里兩萬多名員工按照年齡排序的面試題后，很想記錄下來自己的解題思路，下面綜合考慮到基數(shù)較大和穩(wěn)定性，我們采取歸并排序的算法歸并算法分為兩個兩個靈魂步驟，即拆分歸并我們先把兩萬多名員工的基數(shù)縮小至六名員工的基數(shù)，他們的年齡數(shù) 最近看了一道如何給阿里兩萬多名員工按照年齡排序的面試題后，很想記錄下來自己的解題思路，下面：綜合考慮到基數(shù)較大和穩(wěn)定性，我們采取歸并排序的算法；歸...
摘要：歸并排序是建立在歸并操作上的一種有效的排序算法該算法是采用分治法的一個非常典型的應(yīng)用。若將兩個有序表合并成一個有序表，稱為二路歸并。歸并排序歸并排序是一種非常穩(wěn)定的排序方法，它的時間復(fù)雜度無論是平均，最好，最壞都是。 歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個非常典型的應(yīng)用。將已有序的子序列合并...
摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法樹寫在前面這是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的最后一篇博客，也是在面試中常常會被問到的一部分內(nèi)容排序和搜索。 上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_樹 寫在前面 這是《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》的最后一篇博客，也是在面試中常常會被問到的一部分內(nèi)容：排序和搜索。在這篇博客之前，我每每看到排序頭就是大的，心里想著類似冒泡排序，兩層遍歷啪啪啪就完事了，然后再也無心去深入研究排序相...
閱讀 772·2023-04-25 19:53
閱讀 4408·2021-09-22 15:13
閱讀 2634·2019-08-30 10:56
閱讀 1383·2019-08-29 16:27
閱讀 3019·2019-08-29 14:00
閱讀 2491·2019-08-26 13:56
閱讀 618·2019-08-26 13:29
閱讀 1683·2019-08-26 11:31
