实验5.cpp

设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。 基本要求 ：(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较； (2)待排序表的表长

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"
#include "limits.h"
#define MAXITEM 1000
typedef int KeyType,ElemType;
int count1=0,count2=0,count3=0,count4=0,count5=0,count6=0;
int swap1=0,swap2=0,swap3=0,swap4=0,swap5=0,swap6=0;
typedef struct rec
{
    KeyType key;
    ElemType data;
}sqlist[MAXITEM];

void gennum(sqlist r,sqlist t,int n)
{
	int i;
	srand((unsigned)time(NULL));
	for(i=1;i<=n;i++)
	{	t[i].key=rand()%100;
		r[i].key=t[i].key;
	}
}

void ini(sqlist r,sqlist t,int n)
{
	int i;
	for(i=1;i<=n;i++)
		r[i].key=t[i].key;
}

void BubbleSort(sqlist r,int n)//起泡法r[1]~r[n]
{
    int i,j;
    struct rec w;
    for(i=1;i<=n-1;i++)
       for(j=n;j>=i+1;j--)
       {
          if(r[j].key<r[j-1].key)
          {
             w=r[j];
             r[j]=r[j-1];
             r[j-1]=w;
             swap1++;
          }
          count1++;
       }

}


void InsertSort(sqlist r,int n)//直接插入排序r[1]~r[n]
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        count2++;
        r[0]=r[i];
        j=i-1;
        while(r[0].key<r[j].key)
        {
            r[j+1]=r[j];
            j--;
            count2++;
            swap2++;
        }
        r[j+1]=r[0];
        swap2++;
    }
}

void  SelectSort(sqlist r,int n)//简单选择排序r[1]~r[n]
{
    int i,j,k;
    struct rec temp;
    for(i=1;i<=n-1;i++)
    {
        k=i;
        for(j=i+1;j<=n;j++)
            if(r[j].key<r[k].key){k=j;count3++;}
        if(i!=k)
        {
            temp=r[i];
            r[i]=r[k];
            r[k]=temp;
            swap3++;
        }
    }
}

void QuickSort(sqlist r,int s,int t)//快速排序r[s]~r[t],r[0]空出
{
    int i=s,j=t;
    if(s<t)
    {
        r[0]=r[s];swap4++;
        do
        {
            while(j>i&&r[j].key>=r[0].key){j--;count4++;}
            if(i<j)
            {
                r[i]=r[j];
                i++;
                swap4++;
            }
            while(i<j&&r[i].key<=r[0].key){i++;count4++;}
            if(i<j)
            {
                r[j]=r[i];
                j--;
                swap4++;
            }
        }while(i<j);
        r[i]=r[0];
        swap4++;
        QuickSort(r,s,j-1);
        QuickSort(r,j+1,t);
    }
}

void ShellSort(sqlist r,int n)//希尔排序r[1]~r[n]
{
    int i,j,gap;
    struct rec x;
    gap=n/2;
    while(gap>0)
    {
        for(i=gap+1;i<=n;i++)
        {

            j=i-gap;
            while(j>0)
              if(r[j].key>r[j+gap].key)
              {
                x=r[j];
                r[j]=r[j+gap];
                r[j+gap]=x;
                j=j-gap;
                count5++;
                swap5++;
              }
              else
              {
                j=0;count5++;
              }
        }
        gap=gap/2;
    }
}

void sift(sqlist r,int l,int m)
{
    int i,j;
    struct rec x;
    i=l;
    j=2*i;
    x=r[i];
    while(j<=m)
    {
        if(j<m&&r[j].key<r[j+1].key){j++;count6++;}
        if(x.key<r[j].key)
        {
            r[i]=r[j];
            i=j;
            j=2*i;
            count6++;
            swap6++;
        }
        else {j=m+1;count6++;}
    }
    r[i]=x;
}
void HeapSort(sqlist r,int n)//堆排序r[1]~r[n]
{
    int i;
    struct rec m;
    for(i=n/2;i>=1;i--)sift(r,i,n);
       for(i=n;i>=2;i--)
       {
          m=r[i];
          r[i]=r[1];
          r[1]=m;
          swap6++;
          sift(r,1,i-1);
       }
}

void main()
{
	
	int k,n,a;
	sqlist r,t;
	printf("                 ***************************************\n");
	printf("                 *                                     *\n");
	printf("                 *      * 内部排序算法的性能分析 *     *\n");
	printf("                 *                                     *\n");
	printf("                 ***************************************\n\n");

    printf("-----------------*-------------------------------------*----------------\n");
    printf("**是否执行程序**\n");
	printf("(是) 按 1 键,   (否) 按 0 键\n");
	printf(" 按键为：");
	scanf("%d",&a);
    printf("-----------------*-------------------------------------*----------------\n");

	while(a==1)
	{printf("**请输入要排序的数据的个数：");
	 scanf("%d",&n);
	
	 gennum(r,t,n);
	 printf("\n");

     printf("**随机产生的最初顺序是:\n");
	 for(k=1;k<=n;k++)
	{	printf("%3d",t[k].key);
		if(k%20==0)
			printf("\n");
	}
	 printf("\n");
	 BubbleSort(r,n);
	 printf("\n**排序之后的顺序是:\n");
 	 for(k=1;k<=n;k++)
	{	printf("%3d",r[k].key);
		if(k%20==0)
			printf("\n");
	}
	 printf("\n\n");
	 printf("-------------------------------*分析结果*-------------------------------\n\n");
	 printf("                              **起泡排序**\n");
	 printf("                     比较的次数是: %d,移动的次数是: %d\n\n",count1,swap1);
	
	 ini(r,t,n);
	 InsertSort(r,n);
	 printf("                              **直接插入**\n");
	 printf("                     比较的次数是: %d,移动的次数是: %d\n\n",count2,swap2);
	
 	 ini(r,t,n);
	 SelectSort(r, n);
	 printf("                            **简单选择排序**\n");
	 printf("                     比较的次数是: %d,移动的次数是: %d\n\n",count3,swap3);
	
	 ini(r,t,n);
     QuickSort(r,1,n);
	 printf("                              **快速排序**\n");
	 printf("                     比较的次数是: %d,移动的次数是: %d\n\n",count4,swap4);
	
	 ini(r,t,n);
	 ShellSort(r,n);
	 printf("                              **希尔排序**\n");
	 printf("                     比较的次数是: %d,移动的次数是: %d\n\n",count5,swap5);
	
	 ini(r,t,n);
	 HeapSort(r,n);
	 printf("                               **堆排序**\n");
	 printf("                     比较的次数是: %d,移动的次数是: %d\n\n",count6,swap6);

     printf("-----------------*-------------------------------------*----------------\n");
     printf("**是否继续执行程序**\n");
	 printf(" (是) 按 1 键,   (否) 按 0 键\n");
	 printf(" 按键为： ");
	 scanf("%d",&a);
     printf("-----------------*-------------------------------------*----------------\n");
	}
//	return 0;

}