合并排序：合并函数数组索引零返回多个索引

Question

我想用Javascript实现合并排序作为一种学习经验。我有mergeSort（unsortedArray）函数，它接受一个未经排序的数组，并使用合并排序策略对其进行排序。mergeSort（）调用merge（leftArray,rightArray）,后者将两个数组合并在一起,得到一个数组。

我认为问题出在merge（）函数上。在数组[8,8,7,5,4,6,3,2,1,5,9,8,7,6,5,4,2,3,6,5,4,8]上调用mergeSort时,我得到的结果是:[1,4,2,3,5,5,9,6,7,8,8]。据我所知，问题的根源在于，在merge（）函数中，当对leftarray[0]和righttarray[0]进行比较时，righttarray[0]有时返回多个值，而不仅仅是第一个索引。在我的例子中，它是用2,3和5,9来做的。因此，当代码运行时，有时RightArray[0]=2,3，在数组中拼接2,3之后，RightArray[0]=5,9。以下是merge（）中发生此问题时的情况：

左胸:[4,5,6,7,8,8]
右胸:[1,2,3,5,9]
结果:[]

左房[4,5,6,7,8,8]
右房[2,3,5,9]
结果:[1]

（索引不正确...数组[0]返回两个值）
leftarray[0]=4
righttarray[0]=2,3

左曲面[5,6,7,8,8]
右曲面[2,3,5,9]
结果[1,4]

（索引不正确...数组[0]返回两个值）
leftarray[0]=5
righttarray[0]=2,3

左曲面[5,6,7,8,8]
右曲面[5,9]
结果[1,4,2,3]

...数组[0]索引再次出错，然后返回RightArray[0]=5,9。奇怪的是，如果我在leftarray=[4,5,6,7,8,8]和rightarray[1,2,3,5,9]上调用merge（）函数，而不依赖于mergeSort（），它工作得很好，返回正确的结果，而没有奇怪的索引行为。

null

//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>

null

Answer 1

您需要使用array.prototype.concat()而不是.push()来连接2数组。

.concat组合两个（或更多）数组并返回一个新的数组，而push只是将目标放在数组的末尾，它不会为您连接数组。

如果记录原始结果而不是报警，您将看到

[1,2,3,4,4,数组[2],5,数组1,数组[2],数组1,数组[2],数组[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);
}

null

    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>