java - 使用合并排序与选择排序的比较

Question

我有一个 10 int 的数组，使用选择排序我计算出对整个数组进行排序大约需要 45 次比较，但我不确定使用合并排序需要多少次根据我的计算需要 12 次比较....我在这里是对还是错？

提前致谢

这是合并方法

static void merge(int[] first, int[] second, int[] a)
    {
        int iFirst = 0;
        int iSecond = 0;
        int i = 0; 
        //moving the smaller element into a
        while(iFirst < first.length && iSecond < second.length)
        {
            if(first[iFirst] < second[iSecond])
            {
                a[i] = first[iFirst];
                iFirst++;
            }
            else
            {
                a[i] = second[iSecond];
                iSecond++;
            } 
            i++;             
        }
        counter += i;

        //copying the remaning of the first array
        while(iFirst < first.length)
        {
            a[i] = first[iFirst];
            iFirst++; i++;
        }
        //copying the remaining of second array
        while(iSecond < second.length)
        {
            a[i] = second[iSecond];
            iSecond++; i++;
        }        
    }

Answer 1

要将 n 元素数组与 m 元素数组合并，在最坏的情况下需要进行 n+m-1 比较(最好是 min{m,n})。

因此，当您将 10 元素数组分成两半时，顶层合并需要多达 9 次比较。两个 5 元素的一半需要最多 4 次比较，使得 9 + 2*4 = 17。将 5 元素分成 2 元素部分和 3 元素部分需要多达 1 + 3 次比较，因此最坏的情况总共是 25 次比较(9 + 2*4 + 2*3 + 2*1)。

                10(9)                             9
               /     \
              /       \
             /         \
            /           \
           /             \
          /               \
         /                 \
        5(4)               5(4)                   8
       /   \              /   \
      /     \            /     \
    3(2)     2(1)      3(2)     2(1)              6
   /   \    /   \     /   \    /   \
  2(1)  1  1     1   2(1)  1  1     1             2
 /   \              /   \
1     1            1     1