112

：#include <stdlib.h>#include <stdio.h>#include <time.h> void InsertSort(int a[],in

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#include<conio.h>
#define MAX 10000
//long Max;
long dlta[10000];
int a[MAX+1];
int store[MAX+1];
long  int com0=0,mov0;
long  int com1=0,mov1=0;
long  int com2=0,mov2=0;
long  int com3=0,mov3=0;
long  int com4=0,mov4=0;
long  int com5=0,mov5=0;
double t0,t1,t2,t3,t4,t5;

void randomizeNum(long n)
{//N表示要产生的随机数的数目
 long i;
 
 for(i=0;i<n;i++)
 {
  a[i]=rand()%1000;//控制生成的数据在5000之内
  store[i]=a[i];
  //printf("%5d",store[i]);
  
 }
 printf("\n");
}
void restore(long n)
{
 long i;
 for(i=0;i<n;i++)
 a[i]=store[i];
 //printf("%5d",store[i]);
}
//起泡
void bubblesort(int r[],long n)
{
 long i,j;
 long w;

 //long int com0=0,mov0=0;
for(i=0;i<=n-1;i++)
for(j=n-1;j>=i+1;j--)
{
if(r[j]<r[j-1])
{
 w=r[j];
 r[j]=r[j-1];
 r[j-1]=w;
mov0=mov0+3;
}
com0++;
}

printf("起泡排序　比较次数等于　 %ld,移动次数等于　　 %ld\n",com0,mov0);
}
//直接插入排序

 void insertsort(long r[],long n)
{
 long i,j;
     int watch;
 //long int com1=0,mov1=0;
 for(i=1;i<n;i++)
 { com1++;
  if(r[i]<r[i-1])
  { 
   watch=r[i];
   r[i]=r[i-1];
   mov1++; 
 
   for (j=i-2;watch<r[j];--j)
   { 
     
   r[j+1]=r[j];
 
   mov1++;
   com1++;
   }
  r[j+1]=watch;
  mov1++;
  }
 }


printf("insertsort compare= %ld,move= %ld\n",com1,mov1);
}

 //简单选择排序
 void selectsort(int r[],long n)
 {     
  int i,j,k,temp;
  for(i=0;i<n;i++ )
   {
   k=i;                 
   for (j=i+1;j<n;j++ )
   {com2++;
    if(r[j]<r[k])   
     k=j; 
   }   
  
     temp=r[i];
     r[i]=r[k];
     r[k]=temp;
     mov2=mov2+3;
 
   
  }

  printf("SelectSort compare= %ld,move= %ld\n",com2,mov2);
}


 

 

快速排序


int  Partition(int R[],int n, int low,int high)
{   int pivotkey;
    pivotkey=R[low];
 mov4++;
 while(low<high)
 {
  while( (low<high)&&(R[high]>=pivotkey))
  { --high;
   com4++;
  }
      
  R[low]=R[high];
  mov4++;

   while( (low<high)&&(R[low]<=pivotkey))
   {
    ++low;
    com4++;
   }
  R[high]=R[low];
  mov4++;
 }
 R[low]=pivotkey;
 mov4++;
return low;
}


void QSort(int R[],int n, int low,int high)
{   int pivotloc;
 if (low<high)
 {
  pivotloc=Partition(R,n,low,high);
  QSort(R,n,low, pivotloc-1);
  QSort(R,n, pivotloc+1,high);
 }
}
void QuickSort(int R[],int n)
{  
 QSort(R,n,0,n-1);

 printf("QuickSort compare=%ld,move=%ld\n",com1,mov1);

}

void Sift(int R[], int s, int m)
{//筛选算法
 int temp,j;
 temp=R[s];mov5++;
 for(j=2*s;j<=m;j*=2)
 {    
   if ((j<m)&&(R[j]<R[j+1]))
   {
    j++;
    com5++;
   }
        com5++;
  if (temp>=R[j]) break;
  R[s]=R[j];
  mov5++;

  s=j;
 }
 R[s]=temp;
 mov5++;
}
void HeapSort(int R[],long n)
{    int i,temp;
 for (i=n/2;i>=0;i--)//初始建堆
  Sift(R,i,n);
 for (i=n-1;i>=0;i--)
 {
  temp=R[0];
  R[0]=R[i];
  R[i]=temp;
  mov4=mov5+3;
  Sift(R,0,i-1);
 }

printf("HeapSort compare=%ld,move=%ld\n",com4,mov4);
}

//希尔排序
void ShellInsert(long n,long dk ,int r[])
{int watch;
 long i,j;
 for(i=dk;i<n;i++)
 { com3++;
  if(r[i]<r[i-dk])
  {
   watch=r[i];
   mov3++;
  
   for(j=i-dk;j>=0 && (watch<r[j]);j-=dk)
   {
     r[j+dk]=r[j];
  mov3++;}
  r[j+dk]=watch;
  mov3++;
  }
 }
}
int CalculateT(long n,long dlta[])
{//用于计算希尔排序中的dlta[k]=2^(t-k+1)
 long i,t,k,j;
 long sum=1;
 for(i=1;i;i++)
 {
  sum=sum*2;
  if(sum>n) break;
 }
 t=i-1;
 for(k=1,j=0;k<=t;k++,j++)
 {dlta[j]=(long)pow(2,t-k+1)-1;

 }
 printf("\n"); 
 return t;
}
void ShellSort(long n,long dlta[],long t,int r[])
{   long k;
 

 

 for(k=0;k<t;k++)
 ShellInsert(n,dlta[k],r);
 
  
 printf("ShellSort compare=%ld,move=%ld\n",com3,mov3);
}
 

void print(int a,int num[])
 {
      int i;
   int k=0;
   printf("\n\n\n\t_______________________________________________________________________\n");
   printf("\t|排序方法       |关键字比较次数     |关键字移动次数       |所需时间\n");
   for(i=0;i<a;i++)
   {
    printf("\t\t ____________________________________________________________________  \n");
  
       switch(num[i])
    {
       case 0 :printf("\t|起泡排序            %ld            %ld      %f|",com0,mov0,t0); break;
             case 1 :printf("\t|插入排序            %ld            %ld      %f|",com1,mov1,t1); break;
    case 2 :printf("\t|选择排序            %ld            %ld      %f|",com2,mov2,t2); break;
    case 3 :printf("\t|希尔排序            %ld               %ld      %f|",com3,mov3,t3); break;
    case 4 :printf("\t|快速排序            %ld               %ld      %f|",com4,mov4,t4); break;
    case 5 :printf("\t|堆排序              %ld               %ld      %f|",com5,mov5,t5); break;
    }
    
   }
   printf("\t\t______________________________________________________________________\n");
   printf("\n\t\t★★★★★★★★★★★★★★★★★★★★★\n");
   printf("\t\t★                                      ★\n");
   printf("\t\t★         本组数据排序方法比较表       ★\n");
   printf("\t\t★                                      ★\n");
   printf("\t\t★★★★★★★★★★★★★★★★★★★★★\n");
 }

 
 void Enter_main()  
   {
    printf("\t\t\t   欢迎使用 ! ! !\n");
    printf("\t\t\t***********************\n");
       printf("\t\t\t   |--|         |--|   \n");
       printf("\t\t\t!__|  |_|_|_|_|_|  |__!\n");
       printf("\t\t\t|                     |\n");
       printf("\t\t\t|    ＾         ＾    |\n");
       printf("\t\t\t|    ○         ○    |\n");
       printf("\t\t\t|  ●    ＠＠    ●  |\n");
       printf("\t\t\t|                     |\n");
       printf("\t\t\t|         ●          |\n");
       printf("\t\t\t|_____________________|\n");
       printf("\t\t\t***********************\n");
   
    printf("请按任意键继续……");
   }

 

void main()
{ 

      int i,j,m;
  
   char c='y';
   int n=7;
   int num[6];
   clock_t start,end;   
    
   srand(time(NULL));
   randomizeNum(MAX);
  
   Enter_main();
   getch();
   printf("\n\n\n\n\t\t#############################################\n");
   printf("\t\t         各种排序的实现与效率分析            \n");
   printf("\t\t(1)对起泡排序、直接排序、简单选择排序、快速排\n");
   printf("\t\t   序、希尔排序、堆排序算法进行比较；        \n");
      printf("\t\t(2)数组中的数据是随机产生的,可用多组数据作         \n");
   printf("\t\t   不同数据作比较，比较指标有：关键字参加比较 \n");
   printf("\t  次数和关键字的移动次数和每种算法所需要的时间;\n");
      printf("\t\t(3)输出比较结果。                            \n");
      printf("\t\t#############################################\n");
   printf("请按任意键继续……");
      getch();
 
   while(1)
   { 
       
  
  i=0;
  while(1)
  { 
   while(1)
     {
           printf("\n\t\t请选择要排序的方法(0-5)\n");
           printf("\t\t_________________\n");
                 printf("\t\t| 0.起泡排序    |\n");
           printf("\t\t| 1.插入排序    |\n");
           printf("\t\t| 2.选择排序    |\n");
           printf("\t\t| 3.希尔排序    |\n");
           printf("\t\t| 4.快速排序    |\n");
           printf("\t\t| 5.堆排序      |\n");
                 printf("\t\t_________________\n");
           printf("您的选择:");
           printf("\n");
           scanf("%d",&j);
           while(1)
     {
            if(j>=0&&j<6)
         break;
          printf("你输入有误,请从新输入:");
         scanf("%d",&j);
     }  
              if (j!=n)
     {
         switch(j)
      {
      case 0 : { restore(MAX);
        start=clock();
        bubblesort(a,MAX);
        end=clock();
        t0=(double)(end-start)/CLOCKS_PER_SEC;
        printf("起泡排序所需要的时间为：%f\n",t0);
         }break;
      case 1 : { restore(MAX);
        start=clock();
        insertsort(a,MAX);
        end=clock();
        t1=(double)(end-start)/CLOCKS_PER_SEC;
        printf("插入排序所需要的时间为：%f\n",t1);

         }break;
      case 2 : { restore(MAX);
        start=clock();
        selectsort(a,MAX);
        end=clock();
        t2=(double)(end-start)/CLOCKS_PER_SEC;
        printf("简单选择排序所需要的时间为：%f\n",t2);
         }break;
      case 3 :{ restore(MAX);
              m=CalculateT(MAX,dlta);
                                start=clock();
        ShellSort(MAX,dlta,m,a);
        end=clock();
        t3=(double)(end-start)/CLOCKS_PER_SEC;
        printf("希尔排序所需要的时间为：%f\n",t3);

        }break;
      case 4 :{ restore(MAX);
        start=clock();
        QuickSort(a,MAX);
        end=clock();
        t4=(double)(end-start)/CLOCKS_PER_SEC;
        printf("快速排序所需要的时间为：%f\n",t4);

        }break;
      case 5 :{
                                restore(MAX);
                                start=clock();
        HeapSort(a,MAX);
        end=clock();
        t5=(double)(end-start)/CLOCKS_PER_SEC;
        printf("堆排序所需要的时间为：%f\n",t5);
       
        }break;
     }break;
     
    
     }
                else
     {
      printf("\n\t★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
      printf("\t                           注意!!!!!!!!                             \n");
      printf("\t你选用的排序方法与你上次选用的排序方法相同,请重新选择其他的排序方法:\n");
      printf("\t★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★\n");
      printf("\n");
     }
   }
     n=j;
     num[i]=j;
     i++;
     getchar();
     printf("\n\t\t★★★★★★★★★★★★★★★★★★★★★★\n");
     printf("\t\t★请问还要继续用本组数据进行其他排序吗?(y/n)");
     c=getchar();
     if(c=='n'||c=='N')
     {
                  n=7;
      break;
     }
     printf("\t\t★★★★★★★★★★★★★★★★★★★★★★\n");
  }
        printf("\t\t★★★★★★★★★★★★★★★★★★★★★★\n");
              printf("\n\t\t★★★★★★★★★★★★★★★★★★★\n");
      
     break;
                   
  
 }
              print(i,num);
     getchar();
     getchar();
              system("cls");
  
}