如果给定两个先包含-1的排序数组，则合并为一个排序数组。

Question

如果给定两个数组

arrayOne = [3,6,-1,11,15,-1,32,34,-1,42,-1]
arrayTwo = [1,10,17,56]

两个数组都是排序的，但是array1包含-1在排序的数字之间。

现在的问题是将array2中的数字合并到array1中，以便对array1进行排序，而不应该包含-1。

即

arrayOne =  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]

对于上述问题，我创建了一个算法，如下所示，

step1 :在array2中迭代，与array1中的数字进行比较，如果array2中的数字较少，而在array1中为number，则与交换数字相比。

step2 :继续迭代array1，直到-1发生，现在交换.

step3 :到step1了。

因此，上述算法的工作如下，

step1，

array1 = [3,6,-1,11,15,-1,32,34,-1,42,-1]
array2 = [1,10,17,56]

Step2(交换)：

array1 = [1,6,-1,11,15,-1,32,34,-1,42,-1]
array2 = [3,10,17,56]

Step3(交换)

array1 = [1,3,-1,11,15,-1,32,34,-1,42,-1]
array2 = [6,10,17,56]

Step4(交换)

array1 = [1,3,6,11,15,-1,32,34,-1,42,-1]
array2 = [-1,10,17,56]

Step5(交换)

array1 = [1,3,6,10,15,-1,32,34,-1,42,-1]
array2 = [-1,11,17,56]

继续如上，

以上问题的代码是

puzzle02([3,6,-1,11,15,-1,32,34,-1,42,-1],[1,10,17,56]);

function puzzle02(arrayOne,arrayTwo){   
    var array1Counter = 0,
        array2Counter = 0,       
        hasMinusOneOccurred = false;

    console.log(" array-1 ",arrayOne);
    console.log(" array-2 ",arrayTwo);  


    while(array2Counter < arrayTwo.length){ // iterate through array2

        do{
            if(arrayOne[array1Counter] === -1){ // if -1 occurred in array1
                hasMinusOneOccurred = true;

                // swaping numbers at current position of array1
                // with current position of array2 
                swap(arrayOne,arrayTwo,array1Counter,array2Counter);

                // recheck if the current value is greater than other values
                // of array1
                if(recheckAndSort(arrayOne,array1Counter) === true){
                    array1Counter = -1;// recheck array1 from start
                }else{
                    // recheck the current array1 counter, for doing so go 1 count back
                    // so that even if the counter is incremented it points to current
                    // number itself 
                    array1Counter--; 
                }

            }else if(arrayOne[array1Counter] > arrayTwo[array2Counter]){
                swap(arrayOne,arrayTwo,array1Counter,array2Counter);
            }else{
                array1Counter++;
                continue;   
            }

            array1Counter++;            
        }while(hasMinusOneOccurred === false); // end of do-while

        array2Counter++;
        hasMinusOneOccurred = false;

    }//end of while

    console.log(" Sorted array ",arrayOne);

    function swap(arr1,arr2,arr1Index,arr2Index){
        var temp = arr2[arr2Index];
        arr2[arr2Index] = arr1[arr1Index];
        arr1[arr1Index] = temp;
    }// end of swap 

    // this method is call if -1 occures in array1
    function recheckAndSort(arrayOne,array1Counter){
        var isGreaterVal = true,
            prevCounter = 0,
            nextCounter = 0,
            temp = 0,
            recheckFromStart = false;


        if(array1Counter === 0){ // if -1 occurred at first position of array1.

            // flag to check if -1 occurrec at first position
            // if yes, iterate array1 from start
            recheckFromStart = true; 

            // iterate forward to check wether any numbers are less than current position,
            // if yes than move forward
            for(var j = 0; isGreaterVal; j++){
                nextCounter = j + 1;

                if(arrayOne[nextCounter] === -1){
                    // swaping numbers of array1 between next to current                    
                    swap(arrayOne,arrayOne,nextCounter,j);
                    isGreaterVal = true; 

                }else if(arrayOne[nextCounter] < arrayOne[j]){
                    // swaping numbers of array1 between next to current
                    swap(arrayOne,arrayOne,nextCounter,j);
                    isGreaterVal = true;

                }else{
                    isGreaterVal = false;
                }

            }//end of for

        }else{// if -1 occurred in the middle position of array1 and is been swaped then
            // iterate backwards to check if any number less then current position exists,
            // if yes than shift backwards.
            for(var i = array1Counter; isGreaterVal; i--){
                prevCounter = i - 1;

                if(arrayOne[prevCounter] > arrayOne[i]){

                    // swaping numbers of array1 between previous to current                    
                    swap(arrayOne,arrayOne,prevCounter,i);
                    isGreaterVal = true; 
                }else{
                    isGreaterVal = false;
                }

            }// end of for  
        }

        return recheckFromStart;        
    }// end of recheckAndSort
} // end of puzzle02

以上代码的输出如下

array-1  [ 3, 6, -1, 11, 15, -1, 32, 34, -1, 42, -1 ]
array-2  [ 1, 10, 17, 56 ]
Sorted array  [ 1, 3, 6, 10, 11, 15, 17, 32, 34, 42, 56 ]

请检查我的代码，并给予您宝贵的反馈。

我的逻辑能否如上文所解释的那样得到进一步改进，或者是否有更好的解决上述问题的方法？

请给我建议。

Answer 1

在花了一些时间解决这个问题之后，我有几个想法想和大家分享。

1. 您的代码有一个潜在的错误:如果我向"array-2“添加任何元素，while循环就会变成一个无限循环。
2. 如果您想将某些功能扩展到代码中，请添加第三个数组作为参数。此数组将包含要筛选出的所有值。然后编写一个子例程来过滤掉这些值。
3. 扩展代码的另一种方法是添加一个“检查”函数，该函数可以确保输入的所有数组在运行合并排序算法之前都是按数字顺序排列的。我没有将它添加到我的系统中，但是它可以增加一些现在不存在的健壮性。

我尝试编写这段代码的一个版本，如果您想要进行比较，可以使用看看这个。