合并排序：合并函数数组索引为零返回多个索引
Merge Sort: merge function array index zero returning multiple indexes
我想用 Javascript 实现归并排序作为一种学习经验。我有函数 mergeSort(unsortedArray)，它接受一个未排序的数组并使用合并排序策略对其进行排序。 mergeSort() 调用 merge(leftArray,rightArray)，它将两个已排序的数组合并到一个已排序的数组中。
我认为问题出在 merge() 函数上。在数组上调用 mergeSort 时：[8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,4,2,3,6,5,4, 8] 我得到结果：[1,4,2,3,5,5,9,6,7,8,8]。据我所知，问题的根源是在 merge() 函数中，在比较 leftArray[0] 和 rightArray[0] 时，rightArray[0] 有时会返回多个值，而不仅仅是第一个索引.在我的例子中，它是用 2,3 和 5,9 来做的。所以代码运行时，有时rightArray[0] = 2,3，2,3拼接出数组后rightArray[0]=5,9。以下是出现此问题时 merge() 中发生的情况：
第一步
左数组:[4,5,6,7,8,8]
rightArray:[1,2,3,5,9]
结果：[]
第二步
leftArray[4,5,6,7,8,8]
rightArray[2,3,5,9]
结果：[1]
第三步
（索引不正确...数组[0] 返回两个值）
左数组[0]=4
rightArray[0]=2,3
leftArray[5,6,7,8,8]
rightArray[2,3,5,9]
结果[1,4]
第四步
（索引不正确...数组[0] 返回两个值）
左数组[0]=5
rightArray[0]=2,3
leftArray[5,6,7,8,8]
rightArray[5,9]
结果[1,4,2,3]
...数组[0] 索引再次搞砸了，接下来是returns rightArray[0] = 5,9。奇怪的是，如果我在 leftArray=[4,5,6,7,8,8] 和 rightArray[1,2,3,5,9] 上独立于 mergeSort() 调用我的 merge() 函数，它工作正常并且returns 正确的结果，没有奇怪的索引行为。
//Implement Merge Sort...
function mergeSort(unsortedArray) {
var leftArray = [];
var rightArray = [];
var result = [];
//Base Case of one element
if(unsortedArray.length <= 1){
//alert("Array is size 1 and value: " + unsortedArray);
return unsortedArray;
}
else{
var halfwayPoint = Math.round(unsortedArray.length/2);
//Sepertate unsortedArray into a left and right array
for(var i = 0; i < halfwayPoint; i++){
leftArray.push(unsortedArray[i]);
//alert("leftArray: "+ leftArray + " index i = " + i);
}
for(var i = halfwayPoint; i < unsortedArray.length; i++){
rightArray.push(unsortedArray[i]);
//alert("rightArray" + rightArray + " index i = " + i);
}
//alert("leftArray: " + leftArray + " rightArray: " + rightArray);
leftArray = mergeSort(leftArray);
rightArray = mergeSort(rightArray);
//alert("Arrays before merge = leftArray: " + leftArray + " rightArray: " + rightArray);
result = merge(leftArray, rightArray);
//alert("result: " + result);
}
return result;
}
//Helper function Merge for MergeSort
function merge(leftArray, rightArray)
{
var result = [];
while(leftArray.length > 0 && rightArray.length > 0){
//compare first items of both lists
//alert("top of while loop");
//alert("leftArray[0] = " + leftArray[0] + " rightArray[0] = " + rightArray[0]);
if(leftArray[0] >= rightArray[0]){
result.push(rightArray[0]);
//alert("result after push rightArray[0] " + result + " and rightArray before splice: "+ rightArray);
rightArray.splice(0,1);
//alert("rightArray after splce: " + rightArray);
}
else{
result.push(leftArray[0]);
//alert("result after push leftArray[0] " + result + " and leftArray before splice: "+ leftArray);
leftArray.splice(0,1);
//alert("leftArray after splce: " + leftArray);
}
}
//alert("before leftArray add");
if(leftArray.length > 0){
//alert("went into left array > 0 leftArray: " + leftArray);
result.push(leftArray);
}
//alert("before rightArray add");
if(rightArray.length > 0){
//alert("went into right array > 0 rightArray: " + rightArray);
result.push(rightArray);
}
//alert("result within merge function: " + result);
return result;
}
//Test Case
var unsortedArray = [8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,4,2,3,6,5,4,8];
var sortedArray = mergeSort(unsortedArray);
lert(sortedArray);
//Problem is when Merge sort has left array and right array described below
//the merge function will yield proper result on left array and right array
//if called directly as it is below, however when merge is called through
//mergeSort with leftArray and rightArray as described below it yields
// improperResult below
var leftArray = [4,5,6,7,8,8];
var rightArray = [1,2,3,5,9];
var improperResult= [1,4,2,3,5,5,9,6,7,8,8];
var resultAct = merge(leftArray,rightArray);
alert(resultAct);
<h1>MergeSort Problem</h1>
您需要使用 Array.prototype.concat() 而不是 .push() 来连接 2 arrays.
.concat 组合了 2 个（或更多）数组和 return 一个新的 array，而 push 只是将目标放在 array 的末尾，它不会不会为您连接数组。
如果您记录原始结果而不是警报，您会看到
[1, 2, 3, 4, 4, Array[2], 5, Array1, Array[2], Array1, Array[2],
Array[4]]
很明显，您只是将数组推入了结果。
所以在你的
if(leftArray.length > 0){
result.push(leftArray);
}
if(rightArray.length > 0){
result.push(rightArray);
}
您应该写信给：
if(leftArray.length > 0){
result = result.concat(leftArray);
}
if(rightArray.length > 0){
result = result.concat(rightArray);
}
function mergeSort(unsortedArray) {
var leftArray = [];
var rightArray = [];
var result = [];
//Base Case of one element
if(unsortedArray.length <= 1){
return unsortedArray;
}
else{
var halfwayPoint = Math.round(unsortedArray.length/2);
//Sepertate unsortedArray into a left and right array
for(var i = 0; i < halfwayPoint; i++){
leftArray.push(unsortedArray[i]);
}
for(var i = halfwayPoint; i < unsortedArray.length; i++){
rightArray.push(unsortedArray[i]);
}
leftArray = mergeSort(leftArray);
rightArray = mergeSort(rightArray);
result = merge(leftArray, rightArray);
}
return result;
}
//Helper function Merge for MergeSort
function merge(leftArray, rightArray)
{
var result = [];
while(leftArray.length > 0 && rightArray.length > 0){
//compare first items of both lists
if(leftArray[0] >= rightArray[0]){
result.push(rightArray[0]);
rightArray.splice(0,1);
}
else{
result.push(leftArray[0]);
leftArray.splice(0,1);
}
}
if(leftArray.length > 0){
result = result.concat(leftArray);
}
if(rightArray.length > 0){
result = result.concat(rightArray);
}
return result;
}
//Test Case
var unsortedArray = [8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,4,2,3,6,5,4,8];
var sortedArray = mergeSort(unsortedArray);
alert(sortedArray);
//Problem is when Merge sort has left array and right array described below
//the merge function will yield proper result on left array and right array
//if called directly as it is below, however when merge is called through
//mergeSort with leftArray and rightArray as described below it yields
// improperResult below
var leftArray = [4,5,6,7,8,8];
var rightArray = [1,2,3,5,9];
var improperResult= [1,4,2,3,5,5,9,6,7,8,8];
var resultAct = merge(leftArray,rightArray);
alert(resultAct);
<h1>MergeSort Problem</h1>
我想用 Javascript 实现归并排序作为一种学习经验。我有函数 mergeSort(unsortedArray)，它接受一个未排序的数组并使用合并排序策略对其进行排序。 mergeSort() 调用 merge(leftArray,rightArray)，它将两个已排序的数组合并到一个已排序的数组中。
我认为问题出在 merge() 函数上。在数组上调用 mergeSort 时：[8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,4,2,3,6,5,4, 8] 我得到结果：[1,4,2,3,5,5,9,6,7,8,8]。据我所知，问题的根源是在 merge() 函数中，在比较 leftArray[0] 和 rightArray[0] 时，rightArray[0] 有时会返回多个值，而不仅仅是第一个索引.在我的例子中，它是用 2,3 和 5,9 来做的。所以代码运行时，有时rightArray[0] = 2,3，2,3拼接出数组后rightArray[0]=5,9。以下是出现此问题时 merge() 中发生的情况：
第一步
左数组:[4,5,6,7,8,8]
rightArray:[1,2,3,5,9]
结果：[]
第二步
leftArray[4,5,6,7,8,8]
rightArray[2,3,5,9]
结果：[1]
第三步
（索引不正确...数组[0] 返回两个值）
左数组[0]=4
rightArray[0]=2,3
leftArray[5,6,7,8,8]
rightArray[2,3,5,9]
结果[1,4]
第四步
（索引不正确...数组[0] 返回两个值）
左数组[0]=5
rightArray[0]=2,3
leftArray[5,6,7,8,8]
rightArray[5,9]
结果[1,4,2,3]
...数组[0] 索引再次搞砸了，接下来是returns rightArray[0] = 5,9。奇怪的是，如果我在 leftArray=[4,5,6,7,8,8] 和 rightArray[1,2,3,5,9] 上独立于 mergeSort() 调用我的 merge() 函数，它工作正常并且returns 正确的结果，没有奇怪的索引行为。
//Implement Merge Sort...
function mergeSort(unsortedArray) {
var leftArray = [];
var rightArray = [];
var result = [];
//Base Case of one element
if(unsortedArray.length <= 1){
//alert("Array is size 1 and value: " + unsortedArray);
return unsortedArray;
}
else{
var halfwayPoint = Math.round(unsortedArray.length/2);
//Sepertate unsortedArray into a left and right array
for(var i = 0; i < halfwayPoint; i++){
leftArray.push(unsortedArray[i]);
//alert("leftArray: "+ leftArray + " index i = " + i);
}
for(var i = halfwayPoint; i < unsortedArray.length; i++){
rightArray.push(unsortedArray[i]);
//alert("rightArray" + rightArray + " index i = " + i);
}
//alert("leftArray: " + leftArray + " rightArray: " + rightArray);
leftArray = mergeSort(leftArray);
rightArray = mergeSort(rightArray);
//alert("Arrays before merge = leftArray: " + leftArray + " rightArray: " + rightArray);
result = merge(leftArray, rightArray);
//alert("result: " + result);
}
return result;
}
//Helper function Merge for MergeSort
function merge(leftArray, rightArray)
{
var result = [];
while(leftArray.length > 0 && rightArray.length > 0){
//compare first items of both lists
//alert("top of while loop");
//alert("leftArray[0] = " + leftArray[0] + " rightArray[0] = " + rightArray[0]);
if(leftArray[0] >= rightArray[0]){
result.push(rightArray[0]);
//alert("result after push rightArray[0] " + result + " and rightArray before splice: "+ rightArray);
rightArray.splice(0,1);
//alert("rightArray after splce: " + rightArray);
}
else{
result.push(leftArray[0]);
//alert("result after push leftArray[0] " + result + " and leftArray before splice: "+ leftArray);
leftArray.splice(0,1);
//alert("leftArray after splce: " + leftArray);
}
}
//alert("before leftArray add");
if(leftArray.length > 0){
//alert("went into left array > 0 leftArray: " + leftArray);
result.push(leftArray);
}
//alert("before rightArray add");
if(rightArray.length > 0){
//alert("went into right array > 0 rightArray: " + rightArray);
result.push(rightArray);
}
//alert("result within merge function: " + result);
return result;
}
//Test Case
var unsortedArray = [8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,4,2,3,6,5,4,8];
var sortedArray = mergeSort(unsortedArray);
lert(sortedArray);
//Problem is when Merge sort has left array and right array described below
//the merge function will yield proper result on left array and right array
//if called directly as it is below, however when merge is called through
//mergeSort with leftArray and rightArray as described below it yields
// improperResult below
var leftArray = [4,5,6,7,8,8];
var rightArray = [1,2,3,5,9];
var improperResult= [1,4,2,3,5,5,9,6,7,8,8];
var resultAct = merge(leftArray,rightArray);
alert(resultAct);
<h1>MergeSort Problem</h1>
您需要使用 Array.prototype.concat() 而不是 .push() 来连接 2 arrays.
.concat 组合了 2 个（或更多）数组和 return 一个新的 array，而 push 只是将目标放在 array 的末尾，它不会不会为您连接数组。
如果您记录原始结果而不是警报，您会看到
[1, 2, 3, 4, 4, Array[2], 5, Array1, Array[2], Array1, Array[2], Array[4]]
很明显，您只是将数组推入了结果。
所以在你的
if(leftArray.length > 0){
result.push(leftArray);
}
if(rightArray.length > 0){
result.push(rightArray);
}
您应该写信给：
if(leftArray.length > 0){
result = result.concat(leftArray);
}
if(rightArray.length > 0){
result = result.concat(rightArray);
}
function mergeSort(unsortedArray) {
var leftArray = [];
var rightArray = [];
var result = [];
//Base Case of one element
if(unsortedArray.length <= 1){
return unsortedArray;
}
else{
var halfwayPoint = Math.round(unsortedArray.length/2);
//Sepertate unsortedArray into a left and right array
for(var i = 0; i < halfwayPoint; i++){
leftArray.push(unsortedArray[i]);
}
for(var i = halfwayPoint; i < unsortedArray.length; i++){
rightArray.push(unsortedArray[i]);
}
leftArray = mergeSort(leftArray);
rightArray = mergeSort(rightArray);
result = merge(leftArray, rightArray);
}
return result;
}
//Helper function Merge for MergeSort
function merge(leftArray, rightArray)
{
var result = [];
while(leftArray.length > 0 && rightArray.length > 0){
//compare first items of both lists
if(leftArray[0] >= rightArray[0]){
result.push(rightArray[0]);
rightArray.splice(0,1);
}
else{
result.push(leftArray[0]);
leftArray.splice(0,1);
}
}
if(leftArray.length > 0){
result = result.concat(leftArray);
}
if(rightArray.length > 0){
result = result.concat(rightArray);
}
return result;
}
//Test Case
var unsortedArray = [8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,4,2,3,6,5,4,8];
var sortedArray = mergeSort(unsortedArray);
alert(sortedArray);
//Problem is when Merge sort has left array and right array described below
//the merge function will yield proper result on left array and right array
//if called directly as it is below, however when merge is called through
//mergeSort with leftArray and rightArray as described below it yields
// improperResult below
var leftArray = [4,5,6,7,8,8];
var rightArray = [1,2,3,5,9];
var improperResult= [1,4,2,3,5,5,9,6,7,8,8];
var resultAct = merge(leftArray,rightArray);
alert(resultAct);
<h1>MergeSort Problem</h1>