c - 如何在c中进行合并排序的最坏情况？

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 9 年前。

Improve this question

DataCount 是对数字进行排序的次数。

  int* MakeMWData(int DataCount)
  {

//创建数组

int* Data = (int*)malloc(DataCount*sizeof(int));

int number = 2;
int count = 0;
Data[0] = 1;

//输入数据

int i,j;
for( i = DataCount;; i/=2)
{
    count++;
    for( j = 1; j<DataCount;j++)
    {

//最差归并排序

我认为这是不正确的。

        if(j%i == 0 && j %(i * 2) != 0)
        {
            Data[j] = number;
            number++;
        }
    }
    if(i==1)
        break;
}
for( i = 0; i<DataCount ; i++)
{
    if(Data[i] ==0)
        Data[i] = number;
    number++;
}
return Data;
   }

在主函数中制作最差的数据。

    int* MergeData = MakeMWData(DataCount[i]);

Answer 1

归并排序的工作方式是将数组递归地分成两个数组(logn 次)，直到能够比较元素对。然后它合并递归创建的数组，同时对它们进行排序。

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