c# - 合并2个数组，保持有序，求效率

Question

所以，我发现了一个有趣的问题，给你两个已排序的数组，你的任务是将它们组合成一个新数组并保持其排序。另外，找出程序的效率。我的代码可以工作，但我不确定效率。我认为它是 O(n)，因为我使用 while 循环来迭代数组的每个元素。有小费吗？有没有办法让它变得更有效率？ O(n) 正确吗？这是代码:

class mergesorted{
    static void Main(string[] args){
        int[] x = { 1, 3, 7};
        int[] y = { 2, 4, 5, 6, 15};
        int[] retrieval =  answer(x, y);

        for (int i = 0; i < retrieval.Length; i++){
            Console.WriteLine(retrieval[i]);                
        }
        Console.ReadLine();
    }

    public static int[] answer(int[] x, int[] y)
    {
        int[] a = x;
        int[] b = y;
        int abc = 0; //counter for a
        int abc2 = 0; //counter for b
        int i = 0; //counter for index of new array
        Boolean flagA = true; //if flag changed, array is exhaused
        Boolean flagB = true;
        int[] newarray = new int[a.Length+b.Length]; //so size is 7

        while (abc < a.Length && abc2 < b.Length){
            if (a[abc] < b[abc2]){
                newarray[i] = a[abc];
                abc++;
            }
            else{
                newarray[i] = b[abc2];
                abc2++;
            }

            if (abc >= a.Length){
                flagA = true;
                flagB = false;
            }

            else if (abc2 >= b.Length){
                flagA = false;
                flagB = true;
            }
            i++;
        }

        if (flagA == false){
            while (abc < a.Length){
                newarray[i] = a[abc];
                abc++;
                i++;
            }
        }
        else if (flagB == false){
            while (abc2 < b.Length){
                newarray[i] = b[abc2];
                abc2++;
                i++;
            }
        }
        return (newarray);
    }
}

Answer 1

您有很多多余的测试。但你的算法是 O(N)，因为它接触每个元素一次。你不能做得比这更好(在一般情况下)，因为构建最终数组的时间复杂度为 O(N)。

在特殊情况下，一个数组比另一个数组大得多，并且您有一个 O(1) 插入(或移动)操作，您可以制定一个 O(A log B) 算法，其中 A 是数组的数量较小列表中的条目，B 是较大列表中的条目数。例如，如果一个数组有 1,000,000 个对象，而另一个数组只有 2 个对象，则您可以使用二分搜索来找出在 1,000,000 个对象列表中的位置，将两个对象分别移动到另一个列表中。如果两个列表的大小大致相同，则这没有帮助。