java - 组合排序列表工作 7/10 次

Question

我写了一些代码将两个排序数组组合成一个排序数组。我这样做纯粹是为了学习目的。我编写了自己的代码(没有查看它是如何完成的)并且遇到了一个奇怪的错误。我的代码大约有 7/10 的时间工作，也就是说，它将两个排序的数组正确地推送到一个排序的数组中，它运行了 7/10 次(平均)。当它没有正确排序时，它总是接近数组的末尾，那里的数字顺序不正确。

这是一个不正确的示例输出(使用随机数填充到数组):[3, 16, 19, 24, 27, 33, 35, 41, 52, 55, 59, 67, 74, 77 , 78, 79, 84, 87, 89, 91, 91, 92, 87, 92]

如您所见，错误 (87) 的位置不正确。

这是另一个示例:[0, 4, 7, 8, 10, 11, 15, 16, 24, 25, 31, 32, 38, 54, 58, 62, 63, 66, 67, 70、75、80、62、80]

还有一个:[12, 14, 15, 25, 32, 34, 37, 42, 46, 48, 53, 54, 55, 58, 59, 60, 65, 66, 69, 70, 72, 79, 70, 79]

另一个:[4, 25, 25, 27, 30, 42, 42, 43, 49, 49, 58, 62, 63, 63, 64, 64, 68, 69, 74, 63, 64 , 64, 69, 74]

我只是继续运行它，大约 3/10 的时间我得到了未排序的输出。谁能告诉我我的代码的哪一部分导致了这个？谢谢!

public static int[] mergeSortedLists(int[] arr1, int[] arr2)
    {
        int[] sortedArr = new int[arr1.length + arr2.length];
        int n = 0, m = 0, independentCounter = 0;

        while (n < arr1.length || m < arr2.length)
        {
            if (n != arr1.length && m != arr2.length)
            {

                if (arr1[n] < arr2[m])
                {
                    sortedArr[independentCounter] = arr1[n++];
                }
                else
                {

                    sortedArr[independentCounter] = arr2[m++];
                }
            }
            else if (n == arr1.length)
            {
                copy(m, independentCounter, arr2, sortedArr);
                break;
            }
            else if (m == arr2.length)
            {
                copy(n, independentCounter, arr2, sortedArr);
                break;
            }
            independentCounter++;
        }

        return sortedArr;
    }

    public static void copy(int copyFromUnsortedIndex, int copyToSortedIndex, int[] unsortedArr, int[] sortedArr)
    {

        while (copyToSortedIndex < sortedArr.length && copyFromUnsortedIndex < unsortedArr.length)
        {

            sortedArr[copyToSortedIndex++] = unsortedArr[copyFromUnsortedIndex++];

        }
    }

Answer 1

在您的两个 copy() 调用中，您都指定了 arr2:

        else if (n == arr1.length)
        {
            copy(m, independentCounter, arr2, sortedArr);
            break;
        }
        else if (m == arr2.length)
        {
            copy(n, independentCounter, arr2, sortedArr);
            break;
        }

对于 n 用作源索引的情况，您的意思是 arr1:

        else if (m == arr2.length)
        {
            copy(n, independentCounter, arr1, sortedArr); // <- arr1
            break;
        }

这只会影响数组末尾的数字的原因是这些情况不会发生，直到其中一个输入被完全消耗，这通常发生在末尾。当 arr2 比 arr1 短时，您实际上是在将错误数组的位复制到最后。