1 回答

TA貢獻1871條經(jīng)驗 獲得超13個贊
var mid = lo + (lo + hi) / 2有多個問題。如果您試圖防止溢出,lo + hi則有問題(正確的公式是lo + (hi - lo) / 2)。加lo回來算兩次。/ 2可能會給出一個浮點結(jié)果,這將破壞遞歸邏輯并作為索引失敗。
在設(shè)計方面,我認為沒有理由讓合并排序成為一個有狀態(tài)的類并創(chuàng)建一個實例來對數(shù)組進行排序。這是不必要的開銷,使調(diào)用代碼冗長,并可能引入錯誤。假設(shè)您需要一個類(即使這可能是矯枉過正),使這些方法static更有意義。
this.aux在多個方法調(diào)用和調(diào)用之間持續(xù)存在錯誤已經(jīng)成熟,感覺就像過早的優(yōu)化;將其完全設(shè)置為sort方法的本地可以提高可讀性、封裝性并確保在調(diào)用之間沒有陳舊的數(shù)據(jù)存在。是的,為每一幀創(chuàng)建一個數(shù)組merge很昂貴,但是如果需要優(yōu)化,可以將合并數(shù)組添加到閉包中或作為參數(shù)傳遞?;蛘吆喜⒖梢跃偷赝瓿伞T僬f一次,Array#sort如果性能是您的目標(biāo),這是更好的選擇。
我還發(fā)現(xiàn),使用傳統(tǒng)的數(shù)組長度協(xié)議運行所有拆分,其中l(wèi)o包含mid和lo不包含以及包含和不mid包含的第二個塊更直觀。這避免了我覺得更難推理的和循環(huán)。midhimid + 1hi - 1<=
class MergeSorter {
static merge(a, lo, mid, hi) {
const sorted = [];
let i = lo;
let j = mid;
while (i < mid && j < hi) {
if (a[i] < a[j]) {
sorted.push(a[i++]);
}
else {
sorted.push(a[j++]);
}
}
while (i < mid) sorted.push(a[i++]);
for (let i = 0; i < sorted.length; i++) {
a[lo++] = sorted[i];
}
}
static sort(a, lo=0, hi=a.length) {
if (lo < hi - 1) {
const mid = Math.floor((lo + hi) / 2);
MergeSorter.sort(a, lo, mid);
MergeSorter.sort(a, mid, hi);
MergeSorter.merge(a, lo, mid, hi);
}
}
}
const a = [..."MERGESORTEXAMPLE"];
MergeSorter.sort(a);
console.log(a.join(""));
const rnd = n => ~~(Math.random() * n);
let passes = 0;
const tests = 10000;
for (let i = 0; i < tests; i++) {
const a = Array(rnd(25)).fill().map(() => rnd(25));
const b = a.slice();
MergeSorter.sort(a);
b.sort((a, b) => a - b);
if ("" + a === "" + b) {
passes++;
}
}
console.log(`${passes}/${tests} tests passed`);
添加回答
舉報