javascript - Infinite loop while building mergesort in JavaScript
问题描述
I'm attempting to build out a monkey-patched version of mergeSort
but I'm running into errors every single time. I've ran through debugger a few times and it looks like everything is sorting properly until the last step where I jump to a line in a loader.js file.
Can anyone help me check this out? Thanks in advance!
Array.prototype.mergeSort = function(callback) {
if (this.length <= 1) return this;
if (!callback) {
callback = function(x, y) {
if (x > y) return -1;
else if (x < y) return 1;
else return 0;
};
}
const mid = Math.floor(this.length / 2);
const sortedLeft = this.slice(0, mid).mergeSort(callback);
const sortedRight = this.slice(mid).mergeSort(callback);
return sortedLeft.merge(sortedRight, callback);
};
Array.prototype.merge = function(arr, callback) {
let merged = [];
while (this.length > 0 || arr.length > 0) {
if (callback(this[0], arr[0]) < 0) {
merged.push(arr.shift());
break;
} else if (callback(this[0], arr[0]) >= 0) {
merged.push(this.shift());
break;
}
}
merged = merged.concat(this);
merged = merged.concat(arr);
return merged;
};
解决方案
当任一列表为空时,合并循环应该停止:而不是while (this.length > 0 || arr.length > 0)
你应该写:
while (this.length > 0 && arr.length > 0)
此外,您不应该break
在每次存储到merge
数组之后从循环中,并且两次比较元素是多余的。
这是一个更正的版本:
Array.prototype.merge = function(arr, callback) {
let merged = [];
while (this.length > 0 && arr.length > 0) {
if (callback(this[0], arr[0]) < 0) {
merged.push(arr.shift());
} else {
merged.push(this.shift());
}
}
merged = merged.concat(this);
return merged.concat(arr);
};
但是请注意,您的merge
方法按降序对数组进行排序,并且默认callback
函数也按降序比较元素,从而导致数组巧合地按升序排序。您可能希望简化这一点并null
接受merge
.
这是一个更通用的版本:
Array.prototype.mergeSort = function(callback) {
if (this.length <= 1)
return this;
const mid = this.length >> 1;
const sortedLeft = this.slice(0, mid).mergeSort(callback);
const sortedRight = this.slice(mid).mergeSort(callback);
return sortedLeft.merge(sortedRight, callback);
};
Array.prototype.merge = function(arr, callback) {
let merged = [];
if (callback) {
while (this.length > 0 && arr.length > 0) {
if (callback(this[0], arr[0]) <= 0) {
merged.push(this.shift());
} else {
merged.push(arr.shift());
}
}
} else {
while (this.length > 0 && arr.length > 0) {
if (this[0] <= arr[0]) {
merged.push(this.shift());
} else {
merged.push(arr.shift());
}
}
}
return merged.concat(this).concat(arr);
};
推荐阅读
- go - Golang SHA512 不匹配 OpenSSL SHA512
- flutter - GetX 状态管理
- jestjs - 运行 Jest 测试时使用 jsForce 登录 Salesforce
- code-editor - 在 VMware 中安装 DOMJudge
- ios - NEVPNManager 停止使用 iOS 14 beta
- angular - 如何加载选定的检查垫选择列表
- html - 在 div 中的 brfore 和 after 伪选择器的 css 中块显示
- css - Safari 中按钮子元素的高度与 Chrome 中的行为不同
- coldfusion - 在 ColdFusion CFScript 字符串中转义冒号“:”?
- python - 将在一个列表中找到的对象的属性传递给另一个列表