如何在C中的mergesort中产生最坏的情况?

本文介绍了如何在C中的mergesort中产生最坏的情况?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

DataCount is how many times at sorting numbers.

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; }

在主要功能中产生最差的数据.

Making worst Data in main function.

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

推荐答案

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

The way mergesort works is dividing the array in two arrays, recursively (logn times), untill being able to compare pairs of elements. Then it merges the recursively created arrays also sorting them at the same time.

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

For some sorting algorithms (e.g. quicksort), the initial order of the elements can affect the number of operations to be done. However it doesn't make any change for mergesort as it will have to do exactly the same number of operations anyway: recursively divide into small arrays and then merge them back, in total Θ(nlogn) time.