贪心算法最优合并算法(含源代码)

#include<stdio.h>

#include<stdlib.h>

intgetMin(int[],int);//求最优合并算法比较次数

intgetMax(int[],int);//求最差合并算法比较次数

void quick_sort(int*,int,int);//快速排序，用来对各序列根据序列长度按从小到大排序

int main()

{

int data[100],n,i,min,max;

printf("请输入待合并的序列总个数K:\n");

scanf("%d",&n);

printf("请依次输入这些序列中的元素个数：\n");

for(i=1;i<=n;i++)

scanf("%d",&data[i]);

quick_sort(data,1,n);

max = getMax(data,n);

min = getMin(data,n);

printf("1.最优合并算法的比较次数为：%d\n2.最差合并算法的比较次数为 %d\n",min,max);

system("pause");

return 0;

}

intgetMin(int data[100],int n)

{

int sum=0,i;

if(n==1) return data[n];

for(i=1;i<n;i++)

{

sum+=data[i]+data[i+1]-1;

data[i+1]=data[i]+data[i+1];

quick_sort(data,i+1,n);

}

return sum;

}

intgetMax(int data[],int n)

{

inti,sum=0,amount;//sum记录当前比较次数的总和，amount当前最大序列的长度

amount = data[n];

if(n==1) return amount;

for(i=n-1;i>=1;i--)

{