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

Question

我知道mergesort的最坏情况是O(nlogn),与普通情况相同.

但是,如果数据是升序或降序,则会导致最小比较次数,因此mergesort变得比随机数据快.所以我的问题是:什么样的输入数据产生最大数量的比较,导致mergesort变慢？

这个问题的答案是:

对于某些排序算法(例如快速排序),元素的初始顺序可能会影响要完成的操作数.然而,它不会对mergesort进行任何更改,因为它必须完全执行相同数量的操作:递归地划分为小数组,然后将它们合并回来,总Θ(nlogn)时间.

但这是错误的.在这一点上,我们有两个子阵列,如果初始数据已经排序,我们想要合并它们,我们将只进行n/2次比较.这是第一个子阵列的所有元素,只有第二个数组的第一个元素.但是,我们可以实现更多目标.我正在寻找输入数据.

Answer 1

合并排序的最坏情况将是合并排序必须进行最大比较次数的情况.

所以我将尝试以自下而上的方式构建最坏的情况:

1. 假设排序后的最后一步中的数组是 {0,1,2,3,4,5,6,7}

2. 对于最坏的情况,此步骤之前的数组必须是{0,2,4,6,1,3,5,7}因为这里左子数组= {0,2,4,6}和右子数组= {1,3,5,7}将导致最大比较.(在左右子阵列中存储备用元素)

   原因:数组的每个元素至少会被比较一次.

3. 对于前面的步骤,对于左和右子阵列应用相同的上述逻辑:对于数组{0,2,4,6},最坏的情况是如果前一个数组是{0,4}和{2,6},对于数组{1,3,5,7},最坏的情况是for {1,5}和{3,7}.

4. 现在对前面的步骤数组应用相同的内容: 对于最坏的情况:{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 

Answer 2

算法

我的一位教授给我的一个简洁的算法使用相反的方法解决了这个问题。您可以从基本情况开始并遵循递归模式，而不是将初始数组拆分为越来越小的块。

基本情况是 [1] 和 [2, 1]，它们是大小为1和 的最坏情况数组的示例2。从中您可以为3和构建数组，4如下所示。

1. 取两个大小为n和 的数组m，这样n + m = x，其中 x 是您要查找的大小
2. 组合它们，将较小尺寸的数组放在顶部
3. 将顶部数组中的每个元素加倍
4. 将每个元素加倍并从底部数组中减去 1

使用此算法，这里是大小为3和 的数组的一系列步骤4。

例子

尺寸 3

1. 拿 [1] + [2, 1]
2. 你得到 [1 | 2, 1]
3. [2 | 2, 1]
4. [2 | 3, 1] -> [2, 3, 1]

尺寸 4

1. 拿 [2, 1] + [2, 1]
2. 你得到 [2, 1 | 2, 1]
3. [4, 2 | 2, 1]
4. [4, 2 | 3, 1] -> [4, 2, 3, 1]

尺寸 7

1. 拿 [2, 3, 1] + [4, 2, 3, 1]
2. 你得到 [2, 3, 1 | 4, 2, 3, 1]
3. [4, 6, 2 | 4, 2, 3, 1]
4. [4, 6, 2 | 7, 3, 5, 1] -> [4, 6, 2, 7, 3, 5, 1]

很容易看出如何采用这种方法并轻松构建庞大的数组大小。

程序

这是一个实现此算法的python函数。

import math

def worstCaseArrayOfSize(n):
    if n == 1:
        return [1]
    else:
        top = worstCaseArrayOfSize(int(math.floor(float(n) / 2)))
        bottom = worstCaseArrayOfSize(int(math.ceil(float(n) / 2)))
        return map(lambda x: x * 2, top) + map(lambda x: x * 2 - 1, bottom)