ECMAScript 5 另外新增了兩個「歸併」陣列的方法:reduce() 與 reduceRight()。兩者都會走訪陣列的每一項,差別只在方向:
reduce():從第一項開始,逐項往後走到最後一項。reduceRight():從最後一項開始,逐項往前走到第一項。這兩個方法都接受兩個參數。第一個是在每一項上呼叫的函數,它會收到四個值:前一次的累積值、目前項的值、目前項的索引、陣列物件本身。第二個參數則是可選的初始值。
關鍵在於:該函數回傳的任何值,都會自動成為下一項的「第一個參數」。由於第一次迭代發生在陣列的第二項,所以此時第一個參數會是陣列第一項、第二個參數是陣列第二項;若沒有提供初始值,就以此作為歸併的基礎。
var values = [1, 2, 3, 4, 5];
var sum = values.reduce(function (prev, cur, index, array) {
return prev + cur;
});
alert(sum); // 15
// 結果一樣,只是方向相反
var sum2 = values.reduceRight(function (prev, cur, index, array) {
return prev + cur;
});
alert(sum2); // 15
加法剛好符合交換律,所以兩個方向算出來一模一樣;但如果運算本身有方向性(例如字串串接、陣列攤平、除法),reduce 與 reduceRight 就會得到不同結果,這也是為什麼要同時提供這兩個方法。
說到「歸併」,就不得不提同名的經典演算法。歸併排序(Merge Sort)建立在「歸併操作」之上,是分治法(Divide and Conquer)最典型的應用之一。
它的核心想法是:先把待排序的序列拆成若干子序列,讓每個子序列各自有序,接著再把这些有序子序列合併成一個完整的有序序列。若將兩個有序表合併成一個有序表,即稱為「2-路歸併」。
歸併排序之所以高效,正是因為「合併兩個已排序序列」這件事本身非常單純——只要各自拿一個指標比大小、依序取出即可,整體時間複雜度因此穩定落在 O(n log n)。