对以下两种常用排序算法进行比较：折半插入排序、堆排序(参见教材第九章)，比较各算法的关键字比较次数和关键字移动次数。 （1）对以下两种常用排序算法进行比较：折半插入排序、堆排序； （2）使用题目已经提供的五个数组，比较的指标为有关键字参加的比较次数和关键字移动次数； （3）可以设两个全局变量，分别记录比较与移动次数，设法在程序中适当的地方插入计数操作； （4）在主函数中调用菜单函数调试程序。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define Max 100

int p,q,m,n;


int menu_select();
void Create(int a[],int d[]);
void BinSort(int a[]);
void HeapSort(int a[]);
void crt_heap(int a[]);
void sift(int a[],int k,int m);

int menu_select()	//菜单驱动程序
{
	int sn;
	printf("两种排序算法比较\n");		//显示菜单
	printf("==========================\n");
	printf("1.生成待排序数组\n");
	printf("2.折半插入排序\n");
	printf("3.堆排序\n");
	printf("0.退出程序\n");
	printf("==========================\n");
	printf("请选择0--5:");

	for(;;)		//菜单功能选择
	{
		scanf("%d",&sn);  //输入选项
		getchar();
		if(sn<0 || sn>5)
			printf("\n 输入选择错误，请重新选择 0--3:");
		else
			break;
	}
	return sn;
}

void Create(int a[],int d[])//随机生成数组函数
{
	int c,i,j;
	printf("请输出1-5选择数组:" );
	scanf("%d",&c);
	getchar();
	switch(c){
		case 1:
			for(i=0;i<50;i++)
			a[i]=2*i;
			for(i=50;i<Max;i++)
			a[i]=2*i-1;
			for(j=0;j<Max;j++)
			d[j]=a[j];
			printf("数组1生成成功.\n");
			break;
		case 2:
			for(i=0;i<50;i++)
			a[i]=2*i;
			for(i=50;i<Max;i++)
			a[i]=2*i-3;
			for(j=0;j<Max;j++)
			d[j]=a[j];
			printf("数组2生成成功.\n");
			break;
		case 3:
			for(i=0;i<50;i++)
			a[i]=2*i;
			for(i=Max-1;i>=50;i--)
			a[i]=2*i-1;
			for(j=0;j<Max;j++)
			d[j]=a[j];
			printf("数组3生成成功.\n");
			break;
		case 4:
			for(i=0;i<50;i++)
			a[i]=2*i;
			for(i=Max-1;i>=50;i--)
			a[i]=2*i-3;
			for(j=0;j<Max;j++)
			d[j]=a[j];
			printf("数组4生成成功.\n");
			break;
		case 5:
			for(i=0;i<50;i++)
			a[i]=2*(i+100);
			for(i=50;i<Max;i++)
			a[i]=3*(i-5);
			for(j=0;j<Max;j++)
			d[j]=a[j];
			printf("数组5生成成功.\n");
			break;
	}
}

/*
    TODO: 折半插入排序算法
    功能：编写折半插入排序算法，然后统计关键字的比较次数和移动次数，并输出。
		  关键字a[0]与a[mid]比对一次，关键字比较次数+1，
		  关键字位置互换一次，关键字移动次数+1，
    	  输出语句
    	  printf("折半插入排序\n");
	      printf("关键字比较次数:%d\n",m);
	      printf("关键字移动次数:%d\n",n);
    参数：int a[]是排序查找的数组
    返回值：空
*/
void BinSort(int a[])//折半插入排序算法
{
  printf("折半插入排序\n");
  int i=0,j,x;
  int low,high,mid;
  for(i=2;i<Max;++i){
    x=a[i];
    low=1;
    high=i-1;
    while(low<=high){
        mid=(low+high)/2;
        if(x<a[mid]) {
            high=mid-1;
        }
        else low=mid+1;
        m++;
    }
    for(j=i-1;j>=low;--j){
        a[j+1]=a[j];
         n++;
    }
    a[low]=x;
  }
   printf("关键字比较次数:%d\n",m);
  printf("关键字移动次数:%d\n",n);
}

/*
    TODO: 堆排序算法
    功能：编写堆排序算法，然后统计关键字的比较次数和移动次数，并输出。
		  关键字比较次数在重建堆的方法——sift方法中已计算，函数中传参直接调用即可；
		  关键字通过中间变量进行交换，b=a[1]，a[1]=a[i]，a[i]=b 这样算移动三次位置。
    	  输出语句
		  printf("堆排序\n");
		  printf("关键字比较次数:%d\n",p);
		  printf("关键字移动次数:%d\n",q);
    参数：int a[]是排序查找的数组
    返回值：空
*/
void HeapSort(int a[])//堆排序算法
{
  printf("堆排序\n");
  crt_heap(a);
  int temp,i=0;
  for(i=Max-1;i>=2;i--){
    temp=a[1];
    a[1]=a[i];
    a[i]=temp;
    q+=3;
    sift(a,1,i-1);
  }
  printf("关键字比较次数:%d\n",p);
  printf("关键字移动次数:%d\n",q);
}

void crt_heap(int a[])
{
	int n=Max-1,i;
	for(i=n/2;i>=1;--i)
		sift(a,i,n);
}

void sift(int a[],int k,int m)
{
	int sign=0;
	int t,x,i,j;
	t=a[k];
	x=a[k];
	i=k;
	j=2*i;
	while(j<=m && !sign)
	{
		if(j<m && a[j]<a[j+1])
			j=j+1;
		if(x>=a[j])
			sign=1;
		else{
			a[i]=a[j];
			q++;
			i=j;
			j=2*i;
		}
		p+=2;
	}
	a[i]=t;
}

void main()
{
	int a[Max],d[Max];
	int i;
    m=0;n=0;p=0;q=0;
	for(;;)	 // 无限循环,选择0 退出
	{
		switch(menu_select())	 // 调用菜单函数，按返回值选择功能函数
		{
			case 1:
				printf("1.生成待排序数组\n");
				Create(a,d);
				break;
			case 2:
				printf("2.折半插入排序\n");
				BinSort(a);
				break;
			case 3:
				printf("3.堆排序\n");
				HeapSort(d);
				break;
			case 0:
				printf("0.退出程序\n");
			    return;
		}     // switch语句结束
	}     // for循环结束
}     // main()函数结束