实验五附加

六、 源程序（带注释）

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

#define MAX 100  //定义数组的长度

#define M  5  //希尔排序的趟数

int sort[MAX];  //定义要排序的数组

int move,compare;//移动次数，比较次数

/*********************起泡排序***************************/

void Bubble_Sort()

{

       int sort1[MAX];

       int temp,i;

       move=0,compare=0;//初始化移动次数，比较次数

       for(i=0;i<MAX;i++)       sort1[i]=sort[i];

       printf("*******起泡排序*******/n");

       for(i=1;i<=MAX-1;i++)

              for(int j=0;j<MAX-i;j++)

              {     compare++;

                     if(sort1[j]>sort1[j+1])

                     {temp=sort1[j];sort1[j]=sort1[j+1];sort1[j+1]=temp;move+=3;}

              }

       printf("排序结果为:/n");

       for(i=0;i<MAX;i++)       {printf("%5d",sort1[i]);if((i+1)%10==0) putchar('/n');}

       printf("/n比较次数为:%d/n移动次数为:%d/n",compare,move);

}

/*******************直接插入排序*************************/

void InsertSort()

{     int sort1[MAX];

       int i,temp,j;

       move=0,compare=0;//初始化移动次数，比较次数

       for(i=0;i<MAX;i++)       sort1[i]=sort[i];

       printf("*******直接插入排序*******/n");

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

       {     compare++;

              if(sort1[i]<sort1[i-1])

              {     temp=sort1[i];

                     sort1[i]=sort1[i-1];

                     move+=2;

                     for(j=i-2;j>=0;j--)

                     {     compare++;

                            if(temp<sort1[j])

                            {   sort1[j+1]=sort1[j];

                                   move++;

                            }

                            else

                            {     sort1[j+1]=temp;

                                   move++;

                                   break;

                            }

                     }

                     if(j<0)

                     {sort1[0]=temp; move++;}

              }

       }

       printf("排序结果为:/n");

       for(i=0;i<MAX;i++)       {printf("%5d",sort1[i]);if((i+1)%10==0)putchar('/n');}

       printf("/n比较次数为:%d/n移动次数为:%d",compare,move);

}

/********************简单选择排序****************************/

int selectminkey(int sort1[],int i)

{     int min=i;

       for(int j=i+1;j<MAX;j++)

       {     compare++;

              if(sort1[min]>sort1[j])   min=j;

       }

       return min;

}

void SelectSort()//简单选择排序

{     int sort1[MAX];

       int i,j,temp;

       move=0,compare=0;//初始化移动次数，比较次数

       for(i=0;i<MAX;i++)       sort1[i]=sort[i];

       printf("*******简单选择排序*******/n");

       for(i=0;i<MAX-1;i++)

       {     j=selectminkey(sort1,i);

              if(i!=j)

              {     temp=sort1[i];

                     sort1[i]=sort1[j];

                     sort1[j]=temp;

                     move+=3;

              }

       }

       printf("排序结果为:/n");

       for(i=0;i<MAX;i++)       {printf("%5d",sort1[i]);if((i+1)%10==0)putchar('/n');}

       printf("/n比较次数为:%d/n移动次数为:%d",compare,move);

}

/***********************快速排序**************************/

int partition(int sort1[],int low,int high)

{

       int temp;

       temp=sort1[low];

       move++;

       while(low<high)

       {

              while(low<high&&sort1[high]>=temp)

              {compare++;--high;}

              compare++;

              sort1[low]=sort1[high];

              move++;

              while(low<high&&sort1[low]<=temp)

              {compare++;++low;}

              compare++;

              sort1[high]=sort1[low];

              move++;

       }

       sort1[low]=temp;

       move++;

       return low;

}

void QuickSort(int sort1[],int low,int high)

{     int pivotloc;

       if(low<high)

       {     pivotloc=partition(sort1,low,high);

              QuickSort(sort1,low,pivotloc-1);

              QuickSort(sort1,pivotloc+1,high);

       }

}

void PrintfQuickSort()

{

       int i;

    int sort1[MAX];

       move=0,compare=0;//初始化移动次数，比较次数

    printf("*******快速排序*******/n");

       for(i=0;i<MAX;i++)       sort1[i]=sort[i];

       QuickSort(sort1,0,(MAX-1));

       printf("排序结果为:/n");

       for(i=0;i<MAX;i++)       {printf("%5d",sort1[i]);if((i+1)%10==0)putchar('/n');}

       printf("/n比较次数为:%d/n移动次数为:%d",compare,move);

}

/*******************希尔排序************************/

void ShellInsert(int sort1[],int dk)

{     int sentinel;//哨兵

       for(int i=dk;i<MAX;i++)

       {     compare++;

              if(sort1[i]<sort1[i-dk])

              {     move++;

                     sentinel=sort1[i];

                     for(int j=i-dk;j>=0;j-=dk)

                     {     compare++;

                            if(sentinel<sort1[j])

                            {     move++;

                                   sort1[j+dk]=sort1[j];

                            }

                            else break;

                     }

                     move++;

                     sort1[j+dk]=sentinel;

              }

       }

}

void ShellSort()//希尔排序

{     int sort1[MAX];

       int dlta[M];  //增量序列

       int temp=1,i;

       move=0,compare=0;//初始化移动次数，比较次数

       for(i=0;i<MAX;i++)       sort1[i]=sort[i];

       printf("*******希尔排序*******/n");

       dlta[0]=1;

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

       {     dlta[i]=temp+1;

              temp*=2;

       }

       for(i=M-1;i>=0;i--)

              ShellInsert(sort1,dlta[i]);

       printf("排序结果为:/n");

       for(i=0;i<MAX;i++)       {printf("%5d",sort1[i]);if((i+1)%10==0)putchar('/n');}

       printf("/n比较次数为:%d/n移动次数为:%d",compare,move);

}

/********************堆排序***********************/

void HeapAdjust(int sort1[], int i,int n)

{     int j, k;

       int flag=1;

       j=2*i;

       k=sort1[i];

       move++;

       while (j<=n&&flag==1)

       {     if (j<n&& sort1[j] < sort1[j+1])

              {     compare++;

                     if(sort1[j] < sort1[j+1])  j++;

              }

              compare++;

              if (k >= sort1[j])  flag = 0;

              else

              {     move++;

                     sort1[j/2] = sort1[j];

                     j *= 2;

              }

       }

       move++;

       sort1[j/2] = k;

}

void HeapSort()//堆排序

{     int i;

       int sort1[MAX];

       int temp;

       move=0,compare=0;//初始化移动次数，比较次数

       for(i=0;i<MAX;i++)       sort1[i]=sort[i];

       for (i=MAX/2;i>=0;i--)  HeapAdjust(sort1,i,MAX-1);

 

       for (i=MAX-1;i>0;i--)

       {     move+=3;

              temp= sort1[i];

              sort1[i] = sort1[0];

              sort1[0] = temp;

              HeapAdjust(sort1, 0, i-1);

       }

       printf("*******堆排序*******/n");

       printf("排序结果为:/n");

       for(i=0;i<MAX;i++)       {printf("%5d",sort1[i]);if((i+1)%10==0)putchar('/n');}

       printf("/n比较次数为:%d/n移动次数为:%d",compare,move);

}

/********************菜单函数*********************/

int menu()

{

           int d;

 printf("/n选择排序方法:");

              printf("1:   起泡排序/n");

              printf("2:   直接插入排序/n");

              printf("3:   简单选择排序/n");

              printf("4:   快速排序/n");

              printf("5:   希尔排序/n");

              printf("6:   堆排序/n");

           printf("7:   退出....../n");

              scanf("%d",&d);

              return d;

}

/********************主函数***********************/

void main()

{

       int quit=0;

       int i;

       printf("要排序的随机数组是:/n");

       srand((unsigned)time(NULL));/*用随机函数产生数组*/

       for(i=0;i<MAX;i++)

       {     sort[i]=rand()%199;

              printf("%5d",sort[i]);

              if((i+1)%10==0)putchar('/n');

       }

while(!quit)    

              switch(menu())

              {

              case 1:Bubble_Sort();break;//起泡排序

              case 2:InsertSort();break;//直接插入排序

              case 3:SelectSort();break;//简单选择排序

              case 4:PrintfQuickSort();break;//快速排序

              case 5:ShellSort();break; //希尔排序

              case 6:HeapSort();break;//堆排序

              case 7:quit=1;//退出程序

              }

}