合并排序的最坏情况何时发生？

一尘不染

合并排序的最坏情况何时发生？

algorithm

我知道对mergesort最坏的情况是O（nlogn），与平均情况相同。

但是，如果数据是升序还是降序，这将导致 比较次数最少 ，因此mergesort变得比随机数据快。所以我的问题是：哪种输入数据会产生 最多的比较
结果，从而导致归并排序变慢？

这个问题的答案说：

对于某些排序算法（例如，快速排序），元素的初始顺序可能会影响要执行的操作数量。但是，它不会对mergesort进行任何更改，因为无论如何它都必须执行完全相同数量的操作：递归地划分为小数组，然后将它们合并回去，总共花费Θ（nlogn）时间。

但是，这是错误的。此时，我们有两个子数组，如果要对初始数据进行排序，我们希望将它们合并，那么我们将只有n / 2个比较。那就是第一个子数组的所有元素，而
只有第二个数组的第一个元素。但是，我们可以实现更多目标。我正在寻找输入数据。

阅读 1043

2020-07-28

共1个答案

一尘不染

合并排序的最坏情况是合并排序必须进行 最大数量的比较。

因此，我将尝试以自下而上的方式构建最坏的情况：

假设排序后最后一步的数组是 {0,1,2,3,4,5,6,7}
在最坏的情况下，此步骤之前的数组必须是{0,2,4,6,1,3,5,7}因为此处left subarray = {0,2,4,6}和right subarray = {1,3,5,7}将导致最大的比较。（在左子数组和右子数组中 存储备用元素 ）

原因： 数组的每个元素至少要进行一次比较。

对前面的步骤在左右子数组上应用相同的逻辑：对于数组{0,2,4,6}，最坏的情况是如果前一个数组是{0,4}and {2,6}，对于数组{1,3,5,7}，最坏的情况是for {1,5}和{3,7}。
现在，应用相同的前一步骤数组： 对于最坏的情况 ：{0,4}必须{4,0}，{2,6}必须{6,2}，{1,5}必须是{5,1} {3,7}必须{7,3}。好吧，如果您看清楚这一步是 不必要的， 因为如果set / array的大小为2，那么即使对大小为2的数组进行排序，每个元素也将至少进行一次比较。

现在自上而下分析情况

Applying Merge Sort using Divide and Conquer

Input array arr[] = [4,0,6,2,5,1,7,3]
                           /  \
                          /    \
                  [4,0,6,2] and [5,1,7,3]
                     / \           / \
                    /   \         /   \
                 [4,0] [6,2]    [5,1] [7,3]       Every pair of 2 will be compared atleast once therefore maximum comparison here
                   |     |        |     |
                   |     |        |     |
                 [0,4] [2,6]    [1,5] [3,7]      Maximum Comparison:Every pair of set is used in comparison     
                   \     /        \     /                        
                    \   /          \   /
                 [0,2,4,6]      [1,3,5,7]        Maximum comparison again: Every pair of set compared
                      \             /
                       \           / 
                     [0,1,2,3,4,5,6,7]

现在，您可以对大小为n的任何数组应用相同的逻辑

下面是实现上述逻辑的程序。

注意：以下程序仅对2的幂无效。它是为大小为n的任何数组提供最坏情况的通用方法。您可以自己尝试不同的数组进行输入。

class MergeWorstCase
{
    public static void print(int arr[])
    {
        System.out.println();
        for(int i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
    public static void merge(int[] arr, int[] left, int[] right) {
        int i,j;
        for(i=0;i<left.length;i++)
                arr[i]=left[i];
        for(j=0;j<right.length;j++,i++)
                arr[i]=right[j];
    }

    //Pass a sorted array here
    public static void seperate(int[] arr) {

            if(arr.length<=1)
                return;

            if(arr.length==2)
            {
                int swap=arr[0];
                arr[0]=arr[1];
                arr[1]=swap;
                return;
            }

        int i,j;
        int m = (arr.length + 1) / 2;
        int left[] = new int[m];
        int right[] = new int[arr.length-m];

        for(i=0,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in left subarray
            left[j]=arr[i];

        for(i=1,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in right subarray
            right[j]=arr[i];

        seperate(left);
        seperate(right);
        merge(arr, left, right);
    }
    public static void main(String args[])
    {
        int arr1[]={0,1,2,3,4,5,6,7};
        seperate(arr1);
        System.out.print("For array 1:");
        print(arr1);
        int arr2[]={0,1,2,3,4,5,6,7,8};
        seperate(arr2);
        System.out.print("For array 2:");
        print(arr2);            
    }
}

输出：

For array 1:
4 0 6 2 5 1 7 3 
For array 2:
8 0 4 6 2 5 1 7 3

2020-07-28