内部排序算法比较(原).c

主要是各种排序算法的演示和比较,是数据结构的课程设计,内容详细具体,有文档和代码等

#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 100                         /*设置被测数据的个数*/
static long int c=0;                  /*记录关键字比较次数*/
static long int s=0;                  /*记录关键字移动次数*/
static int R[N];                      /*存放随机产生的被测数据*/

BubbleSort(int R[])        /* 起泡排序，排序元素从R[1]到R[N] */
{ int i,j,t,temp;
  for(i=1;i<=N-1;i++)
  { t=N-i;
    for(j=0;j<=t-1;j++)
    {if(R[j]>R[j+1])      /*比较*/
     { temp=R[j];R[j]=R[j+1];R[j+1]=temp;    /*R[j]与R[j-1]进行交换*/
       s+=3;        /*每交换一次关键字移动次数加3*/
     }
     c++;        /*每比较一次关键字比较次数加1*/
    }
  }

}


void InsertSort(int R[])       /*直接插入排序,排序元素从R[1]到R[N]*/
{
	int i,j;
	for(i=2;i<N;i++)
	{
		R[0]=R[i];   /*把R[i]的值付给监视哨R[0]*/
		j=i-1;
		while(R[0]<R[j])  /*进行元素移动，以便腾出一个位置插入R[i]*/
		{
			R[j+1]=R[j--];
			s++;
			c++;
		}
		R[j+1]=R[0];    /*在j+1位置处插入R[0]*/
		s++;
		c++;
	}
}

void SelectSort(int R[])         /*简单选择排序,排序元素从R[1]到R[N]*/
{
	int i,j,k,temp;
	for(i=0;i<N-1;i++)    /*选择第i小的记录，并交换到位*/
	{
		k=i;
		for(j=i+1;j<N;j++)
		{
                        if(R[j]<R[k])
			   k=j;   /*如果第j个元素少于第k个元素，则把j的值付给k*/
			   c++;   /*进行了一次比较，c+1*/
		}
		if(k!=i)
		{
			temp=R[i];R[i]=R[k];R[k]=temp; /*当k!=i时第k个元素和第i个元素交换*/
			s+=3;    /*每交换一次关键字移动次数加3*/
		}
	}
}

void QuickSort(int lo,int hi)      /*快速排序,排序元素从R[lo]到R[hi]*/
{
   int i,j;
   i=lo,j=hi;
   if(lo<hi)
   {
      R[0]=R[lo];s++;  /*用R[0]作枢轴记录*/
      do      /*从数组的两端交替地向中间扫描*/
      {
          while(j>i&&R[j]>=R[0])
          {  j--;c++;  }
             c++;
          if(i<j)
          {
             R[i]=R[j];i++;s++; /*将比枢轴记录大的记录交换到高端*/
          }
          while(i<j&&R[i]<=R[0])
          { i++;c++; }
             c++;
          if(i<j)
          {
             R[j]=R[i];j--;s++;  /*将比枢轴记录小的记录交换到低端*/
          }
       }while(i<j);
    R[i]=R[0];s++;       /*枢轴记录到位*/
    QuickSort(lo,j-1);   /*对低于子表递归排序*/
    QuickSort(j+1,hi);   /*对高于子表递归排序*/
   }
}

void ShellSort(int R[])       /*希尔排序,排序元素从R[1]到R[N]*/
{
  int i=4,h=1;     /*增量置初值*/
  int j,temp;
  while (i<=100)
   { i=i*2;h=2*h+1;}
  while(h!=0){
  i=h/2;
  while(i<=N)
  { j=i-h;
    while(j>0&&(R[j+h]<R[j]))
    { temp=R[j];R[j]=R[j+h];R[j+h]=temp;  /*将R[j]与R[j+h]进行交换*/
      j=j-h;
      s+=3;c++;
    }c++;
    i++;
  }
  h=(h-1)/2;  /*减少增量*/
 }
}

void sift(int R[],int l,int m)     /*堆排序辅助函数*/
{
   int i,j;int temp;
   i=l;j=2*i;       /*R[j]是R[i]的左孩子*/
   temp=R[i];s++;
   while(j<=m)     /*若右孩子较大，则把j修改为右孩子的下标*/
   {
     if(j<m&&R[j]<R[j+1])j++;c++;
     if(temp<R[j])
     {
        R[i]=R[j];   /*将R[j]调到父亲的位置上*/
        i=j;         /*修改i和j的值，以便继续向下筛选*/
        j=2*i;
        s++;
     }
     else j=m+1;   /*筛选运算完成，令j=m+1,以便中止循环*/
     c++;
   }
   R[i]=temp;  /*被筛选结点的值放入最终位置*/
   s++;
}

void HeapSort(int n)           /*堆排序，排序元素从R[1]到R[N]*/
{
   int i;
   int temp;
   for(i=n/2;i>=1;i--)
    sift(R,i,n);  /*建立初始堆*/
     for(i=n;i>=2;i--)     /*进行n-1次循环，完成堆排序*/
     { temp=R[i];R[i]=R[1];R[1]=temp;   /*将第一个元素同当前区间内最后一个元素对换*/
       s+=3;
       sift(R,1,i-1);   /*筛选R[]的结点，得到i-1个结点的堆*/
     }
}

void BeforeSort(int data[])    /*每个排序算法在使用前调用，用于计数器复零*/
{
        int i;
        for(i=0;i<N;i++)
        { R[i]=data[i]; }  /*把data[i]中的元素全部付给R[i]*/
        c=0;s=0;      /*每次进行排序前计数器复零*/
}

void Compare()
{
        int i;
	int data[1000];  /*用于存放R[N]比较前的数据，待R[N]排序后重新付给R[N]*/
        for(i=0;i<N;i++)
	{ R[i]=rand();}  /*利用随机函数rand产生待测数据并用数组R[i]来储存*/
 	for(i=0;i<N;i++)
        { data[i]=R[i];}
        printf("\n\t     ====================================================\n");
        printf("\t        内部排序算法 |  关键字比较次数 |  关键字移动次数  \n");
	printf("\t     |--------------------------------------------------|\n");
        c=0;s=0;
        BubbleSort(R);
        printf("\t          起泡排序   |      %-7ld    |       %-7ld      \n",c,s);
        printf("\t     |--------------------------------------------------|\n");

        BeforeSort(data);
        InsertSort(R);
        printf("\t        直接插入排序 |      %-7ld    |       %-7ld      \n",c,s);
        printf("\t     |--------------------------------------------------|\n");

        BeforeSort(data);
	SelectSort(R);
	printf("\t        简单选择排序 |      %-7ld    |       %-7ld        \n",c,s);
	printf("\t     |--------------------------------------------------|\n");

        BeforeSort(data);
	QuickSort(1,N);
	printf("\t          快速排序   |      %-7ld    |       %-7ld        \n",c,s);
	printf("\t     |--------------------------------------------------|\n");

        BeforeSort(data);
        ShellSort(R);
        printf("\t          希尔排序   |      %-7ld    |       %-7ld        \n",c,s);
        printf("\t     |--------------------------------------------------|\n");

        BeforeSort(data);
        HeapSort(N);
        printf("\t         堆  排  序  |      %-7ld    |       %-7ld        \n",c+1,s);
        printf("\t     ====================================================\n");
}

main()
{
       char ch1,ch2;
       int i,m;
       textbackground(GREEN);  /*改变背景颜色*/
       textcolor(BLACK);      /*改变字体颜色*/
       clrscr();           /*清屏*/
       do
       {
            clrscr();
            printf("\t   =========================================================\n\n");
            printf("\t                只 用 一 组 数 据 比 较 请 按 'A'           \n");
            printf("\t                使 用 五 组 数 据 比 较 请 按 'F'           \n");
            printf("\t                使 用 多 组 数 据 比 较 请 按 'M'           \n");
	    printf("\t                退 出 系 统 请 按             'Q'           \n\n");
            printf("\t   =========================================================\n");
            printf("\t   =========================================================\n");
            scanf("%c",&ch1);   /*从键盘输入一个字符，用以选择所要进行的操作*/
            getchar();     /*接收一个回车*/
            switch(ch1)
              {
                 case'a':
                 case'A':     Compare();break;
                 case'f':
                 case'F':     for(i=0;i<5;i++)                    /*利用循环进行五次比较*/
                              {
                                  Compare();
                                  printf("\n请按回车键继续:");
                                  getchar();   /*从键盘接收一个回车,使所得结果可以分面显示*/
                              }break;
                 case'm':
                 case'M':     printf("你想使用多少组数据进行比较：");
                              scanf("%d",&m);
                              getchar();     /*从键盘接收一个回车,使所得结果可以分面显示*/
                              for(i=0;i<m;i++)                   /*利用循环进行多次比较*/
                               {
                                  Compare();
                                  printf("\n请按回车键显示下一组结果:");
                                  getchar();  /*从键盘接收一个回车*/
                              }break;
                 case'q':
                 case'Q':
                                printf("\n真的要退出系统 ？");
                                break;
              }
	    printf("\n还要继续进行排序比较吗？(Y/N): ");
            ch2=getchar();	/*从键盘输入一个字符，用以选择所要进行的操作*/
	    getchar();      /*从键盘接收一个回车*/
	}while(ch2!='N'&&ch2!='n');
	printf("\n\t\t Exit successfully!\nPress any key!");getch();
}