内部排序算法的实现与比较.doc

实验四：内部排序算法的实现与比较
一、 问题描述
1． 实验题目：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
2． 基本要求：（1）对常用的内部排序算法进行比较：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。
（2利用随机函数产生N（N=30000）个随机整数，作为输入数据作比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。
（3)对结果作出简要分析。
3． 测试数据：随机函数产生。
二、 需求分析
1． 程序所能达到的基本可能：通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。
2． 输入的形式及输入值范围 ：随机函数产生的N（N=30000）个随机整数。
3． 输出的形式：输出各种排序算法的关键字参加的比较次数和关键字的移动次数。并按从小到大排列。
4． 测试数据要求：随机函数产生的N（N=30000）个随机整数。
三、 概要设计
1. 所用到得数据结构及其ADT
为了实现上述功能，应以一维数组表示集合数据类型。
int s[N];
int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0};
基本操作：
数组赋值：
for(i=1;i<N;i++)
{
s[i]=rand()%100;
printf("%d\t",s[i]);
}
void copys(int S[],int RS[],int n)//将s[]的值赋给RS[],
void SelectSort(int RS[],int n) //直接选择排序
void BubbleSort(int RS[],int n)//冒泡排序
void InsertSort(int RS[],int n) //直接插入排序
int QuickSort(int RS[],int low,int high)//快速排序
void QuickSortprint(int RS[],int n)//输出快速排序后的结果
void Shellsert(int RS[],int m,int n)//一趟希尔排序，按间隔m划分子序列
void Shellsort(int RS[],int n)//希尔排序
void Merge(int RS[],int low,int mid,int high)//将两个有序序列归并为一个有序序列
void MSort(int RS[],int low,int high)//归并排序
2. 主程序流程及其模块调用关系

void SelectSort(int RS[],int n) //直接选择排序模块
void BubbleSort(int RS[],int n)//冒泡排序模块
void InsertSort(int RS[],int n) //直接插入排序模块

int QuickSort(int RS[],int low,int high)//快速排序模块

void Shellsert(int RS[],int m,int n)//一趟希尔排序，按间隔m划分子序列

void Shellsort(int RS[],int n)//希尔排序模块

void Merge(int RS[],int low,int mid,int high)//将两个有序序列归并为一个有序序列
模块调用
四、 详细设计
1. 实现每个操作的伪码，重点语句加注释
1）void copys(int S[],int RS[],int n)//数组复制
{
int i;
for(i=1;i<n;i++)
RS[i]=S[i];
}
2） 直接选择排序
void SelectSort(int RS[],int n) //直接选择排序
{
int i,j,k;
for(i=1;i<n;i++)
{
k=i;
for(j=i+1;j<=n;j++)
{
if(RS[j]<RS[k])
k=j;
compare[0]++;
}
if(k!=i)
{
RS[0]=RS[k];
RS[k]=RS[i];
RS[i]=RS[0];
move[0]+=3;
}
}
printf("直接选择排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[0],move[0]);
printf("\n");
}
3） 冒泡排序
void BubbleSort(int RS[],int n)//冒泡排序
{
int i,j,flag;
for(i=1;i<=n;i++)
{
flag=True;
for(j=1;j<=n-i;j++)
{ if(RS[j+1]<RS[j])
{
flag=False;
RS[0]=RS[j];
RS[j]=RS[j+1];
RS[j+1]=RS[0];
move[1]+=3;
}
compare[1]++;
}
if(flag==True)
break;
}
printf("冒泡排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[1],move[1]);
printf("\n");

}
4） 直接插入排序
void InsertSort(int RS[],int n) //直接插入排序
{
int i,j;
for(i=2;i<=n;i++)
{
RS[0]=RS[i];
j=i-1;
move[2]++;
while(RS[0]<RS[j])
{
compare[2]++;
RS[j+1]=RS[j];
move[2]++;
j--;
}
compare[2]++;
RS[j+1]=RS[0];
move[2]++;
}
printf("直接插入排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[2],move[2]);
printf("\n");
}

5） 快速排序
int QuickSort(int RS[],int low,int high)//快速排序
{
int i,j,n;
n=high;
i=low;
j=high;
RS[0]=RS[i];
move[3]++;
while(i<j)
{
while(RS[j]>=RS[0]&&j>i)

{
j--;
compare[3]++;

}
compare[3]++;
if(j>i)
{
RS[i]=RS[j];
move[3]++;
i++;

}
while(RS[i]<=RS[0]&&j>i)
{
i++;
compare[3]++;

}
compare[3]++;
if(j>i)
{
RS[j]=RS[i];
move[3]++;
j--;

}
}
RS[i]=RS[0];
move[3]++;
if(low<i)
QuickSort(RS,low,i-1);
if(i<high)
QuickSort(RS,j+1,high);

}
6） 输出快速排序后的结果
void QuickSortprint(int RS[],int n)//输出快速排序后的结果
{ int i;
QuickSort(RS,1,n);
printf("快速排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[3],move[3]);
printf("\n");
}
7） 一趟希尔排序，按间隔m划分子序列
void Shellsert(int RS[],int m,int n)//一趟希尔排序，按间隔m划分子序列
{
int i,j,temp;
for(i=m;i<=n/m;i++)
{
temp=RS[i];
j=i;
while(j>=m&&temp<RS[j-m])
{
compare[4]++;
RS[j]=RS[j-m];
move[4]++;
j-=m;
}
RS[j]=temp;
move[4]++;
}
}
8） 希尔排序
void Shellsort(int RS[],int n)//希尔排序
{
int m,i;
m=n/2;
while(m>=1)//循环直到m为0
{
Shellsert(RS,m,n);
m=(m==2?1:(m/2));//缩小增进量
}
printf("希尔排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[4],move[4]);
printf("\n");
}
9） 将两个有序序列归并为一个有序序列
void Merge(int RS[],int low,int mid,int high)//将两个有序序列归并为一个有序序列
{
int i,j,k;
int n1,n2;
i=low;
j=mid+1;
k=low;
while(i<=mid&&j<=high)//两两比较
{
if(RS[i]<=RS[j])
{
D[k]=RS[i];
i++;
k++;
}
else
{
D[k]=RS[j];
j++;
k++;
}
compare[5]++;
move[5]++;
}
if(i<=mid)
for(n1=k,n2=i;n1<=high&&n2<=mid;n1++,n2++)
{
D[n1]=RS[n2];
move[5]++;
}
else
for(n1=k,n2=j;n1<=high&&n2<=high;n1++,n2++)
{
D[n1]=RS[n2];
move[5]++;
}
for(mid=low;mid<=high;mid++)
{
RS[mid]=D[mid];
move[5]++;
}
}
10） 归并排序
void MSort(int RS[],int low,int high)//归并排序
{
int mid;
if(low<high)
{
mid=(low+high)/2;
MSort(RS,low, mid);
MSort(RS, mid+1,high);
Merge(RS,low,mid,high);
}
}
11） 主函数
void main()
{
int i,j,s[N];
time_t rawtime;
struct tm * timeinfo;
time (&rawtime);
timeinfo = localtime (&rawtime);

printf(" 实验名称：实验四：内部排序算法的实现与比较\n");
printf(" 学号：031350102\n");
printf(" 姓名：王亚文\n");
printf("=============================================\n");
printf("程序运行开始，");
printf("Current local time and date:%s",asctime(timeinfo));
printf("产生的随机数为：\n");
for(i=1;i<N;i++)
{
s[i]=rand()%100;
printf("%d\t",s[i]);
}
printf("\n");
do
{
copys(s,RS,N);
printf("请选择所需排序方法：");
printf("\n");
printf("1.选择法 ,2.冒泡法 ,3.插入法 ,4.快速法 , 5.希尔排序法 ,6.归并排序法，7.输出比较信息，8.退出\n");
scanf(" %d",&j);
switch(j)
{
case 1:
SelectSort(RS,N-1);
break;
case 2:
BubbleSort(RS,N-1);
break;
case 3:
InsertSort(RS,N-1);
break;
case 4:
QuickSortprint(RS,N-1);
break;
case 5:
Shellsort(RS,N-1);
break;
case 6:
MSort(RS,1,N-1);
printf("归并排序后的结果：");
for(i=1;i<N;i++)
printf("%d\t",D[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[5],move[5]);
printf("\n");
break;
case 7:
SelectSort(compare,5);
SelectSort(move,5);
printf("关键字参加的比较次数:\n");
for(i=1;i<=5;i++)
printf("%d\t",compare[i]);
printf("\n");
printf("关键字的移动次数：\n");
for(i=1;i<=5;i++)
printf("%d\t",move[i]);
printf("\n");
break;
case 8:
printf("Current local time and date:%s",asctime(timeinfo));
exit(0);
break;
}
}while(1);

}
五、 调试分析
1. 设计与调试过程中遇到的问题分析、体会
调试过程：由于本次程序设计的数据和模块比较多，所以采用分块调试的方法，在编写完一个内部排序算法后，为了验证是否排序成功以及所输出的关键字比较次数和移动次数是否正确，采用先定义一个需要排序9个数字的数组，S[10]={0，1，2，3，4，5，6，7，8，9}和S[10]={0，9，8，7，6，5，4，3，2，1},用这两个数组检验程序的正确性与否。调试步骤，程序及相关结果如下：
1） 直接选择排序：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
void SelectSort(int RS[],int n) //直接选择排序
{
int i,j,k,move=0,compare=0;
for(i=1;i<n;i++)
{
k=i;
for(j=i+1;j<=n;j++)
{
if(RS[j]<RS[k])
k=j;
compare++;
}
if(k!=i)
{
RS[0]=RS[k];
RS[k]=RS[i];
RS[i]=RS[0];
move+=3;
}
}
printf("直接选择排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare,move);
printf("\n");
}
void main()
{
int s[10]={0,1,2,3,4,5,6,7,8,9};
SelectSort(s,9);
}
s[10]={0,1,2,3,4,5,6,7,8,9};
S[10]={0,9,8,7,6,5,4,3,2,1}

2)冒泡排序
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define False 0
#define True 1
void BubbleSort(int RS[],int n)//冒泡排序
{
int i,j,flag,move=0,compare=0;
for(i=1;i<=n;i++)
{
flag=True;
for(j=1;j<=n-i;j++)
{ if(RS[j+1]<RS[j])
{
flag=False;
RS[0]=RS[j];
RS[j]=RS[j+1];
RS[j+1]=RS[0];
move+=3;
}
compare++;
}
if(flag==True)
break;
}
printf("冒泡排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare,move);
printf("\n");

}

void main()
{
int s[10]={0,1,2,3,4,5,6,7,8,9};
BubbleSort(s,9);
}
s[10]={0,1,2,3,4,5,6,7,8,9}
s[10]={0,9,8,7,6,5,4,3,2,1};

3） 直接插入排序
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define False 0
#define True 1
void InsertSort(int RS[],int n) //直接插入排序
{
int i,j,compare=0,move=0;
for(i=2;i<=n;i++)
{
RS[0]=RS[i];
j=i-1;
move++;
while(RS[0]<RS[j])
{
compare++;
RS[j+1]=RS[j];
move++;
j--;
}
compare++;
RS[j+1]=RS[0];
move++;
}
printf("直接插入排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare,move);
printf("\n");
}

void main()
{
int s[10]={0,9,8,7,6,5,4,3,2,1};
InsertSort(s,9);
}
s[10]={0,9,8,7,6,5,4,3,2,1};

s[10]={0,1,2,3,4,5,6,7,8,9};

4） 快速排序
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define False 0
#define True 1
int compare[6]={0},move[6]={0};
int QuickSort(int RS[],int low,int high)//快速排序
{
int i,j,n;
n=high;
i=low;
j=high;
RS[0]=RS[i];
move[3]++;
while(i<j)
{
while(RS[j]>=RS[0]&&j>i)

{
j--;
compare[3]++;

}
compare[3]++;
if(j>i)
{
RS[i]=RS[j];
move[3]++;
i++;

}
while(RS[i]<=RS[0]&&j>i)
{
i++;
compare[3]++;

}
compare[3]++;
if(j>i)
{
RS[j]=RS[i];
move[3]++;
j--;

}
}
RS[i]=RS[0];
move[3]++;
if(low<i)
QuickSort(RS,low,i-1);
if(i<high)
QuickSort(RS,j+1,high);

}
void QuickSortprint(int RS[],int n)//输出快速排序后的结果
{ int i;
QuickSort(RS,1,n);
printf("快速排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[3],move[3]);
printf("\n");
}

void main()
{
int s[10]={0,9,8,7,6,5,4,3,2,1};
QuickSortprint(s,9);
}
s[10]={0,9,8,7,6,5,4,3,2,1};

5） 希尔排序
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define False 0
#define True 1
int compare[6]={0},move[6]={0};
void Shellsert(int RS[],int m,int n)//一趟希尔排序，按间隔m划分子序列
{
int i,j,temp;
for(i=m;i<=n/m;i++)
{
temp=RS[i];
j=i;
while(j>=m&&temp<RS[j-m])
{
compare[4]++;
RS[j]=RS[j-m];
move[4]++;
j-=m;
}
RS[j]=temp;
move[4]++;
}
}
void Shellsort(int RS[],int n)//希尔排序
{
int m,i;
m=n/2;
while(m>=1)//循环直到m为0
{
Shellsert(RS,m,n);
m=(m==2?1:(m/2));//缩小增进量
}
printf("希尔排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[4],move[4]);
printf("\n");
}

void main()
{
int s[10]={0,9,8,7,6,5,4,3,2,1};
Shellsort(s,9);
}
s[10]={0,9,8,7,6,5,4,3,2,1};

s[10]={0,1,2,3,4,5,6,7,8,9};

6） 归并排序
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define False 0
#define True 1
int compare[6]={0},move[6]={0},D[10]={0};
void Merge(int RS[],int low,int mid,int high)//将两个有序序列归并为一个有序序列
{
int i,j,k;
int n1,n2;
i=low;
j=mid+1;
k=low;
while(i<=mid&&j<=high)//两两比较
{
if(RS[i]<=RS[j])
{
D[k]=RS[i];
i++;
k++;
}
else
{
D[k]=RS[j];
j++;
k++;
}
compare[5]++;
move[5]++;
}
if(i<=mid)
for(n1=k,n2=i;n1<=high&&n2<=mid;n1++,n2++)
{
D[n1]=RS[n2];
move[5]++;
}
else
for(n1=k,n2=j;n1<=high&&n2<=high;n1++,n2++)
{
D[n1]=RS[n2];
move[5]++;
}
for(mid=low;mid<=high;mid++)
{
RS[mid]=D[mid];
move[5]++;
}
}
void MSort(int RS[],int low,int high)//归并排序
{
int mid;
if(low<high)
{
mid=(low+high)/2;
MSort(RS,low, mid);
MSort(RS, mid+1,high);
Merge(RS,low,mid,high);
}
}
void main()
{
int s[10]={0,9,8,7,6,5,4,3,2,1},i;
MSort(s,1,9);
printf("归并排序后的结果：");
for(i=1;i<10;i++)
printf("%d\t",D[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[5],move[5]);
printf("\n");

}
s[10]={0,9,8,7,6,5,4,3,2,1}；

调试过程中遇到的问题：
1）这个内部排序算法的实现与比较程序设计中，大部分排序算法在书上已经给了详细的程序只需要稍加更改，所以在编写排序程序时并没有太大的问题，唯一的问题是for(mid=low;mid<=high;mid++)
{
RS[mid]=D[mid];
move[5]++;
}
这段程序一开始书上是放在MSort这个程序中，但是我放在这个程序里输出的排序并不是按照升序排列的，将这段程序改在merge里，程序就能正常输出了，还有一个问题是随机数产生的数字是放在数组里的，执行完第一个排序后再想去执行下一个排序程序时再用原来的数组就已经不是利用随机函数产生的数组了而是经过排序后形成的有序数组，这就影响了下一个程序的正常运行，他所输出的关键字的比较次数和移动次数就不是我们所想的随机函数产生的数组排序时的比较次数和移动次数，为了解决这个问题考虑另外定义一个数组，先利用随机函数产生一个随机数组，每次执行排序前都将随机数组中的数值赋给另一个数组，对另外的数组执行排序程序，这就可以有效解决输出的关键字的比较次数和移动次数不对的问题。这样第一步显示保证每个程序都可以将一个无序的序列排序成为有序序列。
2）在完成了第一步之后就可以进行第二部，进行关键字的比较次数和移动次数的计算，一开始我是将每一个程序中都定义一个compare和move值，这种办法在前几个程序中并没有什么问题，也没有什么不方便，但在之后一个函数需要调用另一个函数时，因为一个函数只能返回一个值，这个对于这个需要返回两个值的程序就不适用了，所以就考虑定义了两个数组，int compare[6]={0},move[6]={0}，这样就解决了这个不能再一个程序中返回两个值得问题，同时也大大简化了后面需要对各种内部排序算法所产生的关键字的比较次数和移动次数的排序与输出，一举两得。
这个程序是通过随机数据产生N个随机数，作为输入数据作比较；对常用的内部排序算法：直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序进行比较：比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换记为3次移动）。最后结果输出各种排序算法的关键字参加的比较次数和关键字的移动次数，并按从小到大排列。
六、 测试结果

七、 附录
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
#define N 100
#define False 0
#define True 1
int compare[6]={0},move[6]={0},D[N]={0},RS[N]={0};
void copys(int S[],int RS[],int n)
{
int i;
for(i=1;i<n;i++)
RS[i]=S[i];
}
void SelectSort(int RS[],int n) //直接选择排序
{
int i,j,k;
for(i=1;i<n;i++)
{
k=i;
for(j=i+1;j<=n;j++)
{
if(RS[j]<RS[k])
k=j;
compare[0]++;
}
if(k!=i)
{
RS[0]=RS[k];
RS[k]=RS[i];
RS[i]=RS[0];
move[0]+=3;
}
}
printf("直接选择排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[0],move[0]);
printf("\n");
}
void BubbleSort(int RS[],int n)//冒泡排序
{
int i,j,flag;
for(i=1;i<=n;i++)
{
flag=True;
for(j=1;j<=n-i;j++)
{ if(RS[j+1]<RS[j])
{
flag=False;
RS[0]=RS[j];
RS[j]=RS[j+1];
RS[j+1]=RS[0];
move[1]+=3;
}
compare[1]++;
}
if(flag==True)
break;
}
printf("冒泡排序后的结果：");
for(i=1;i<=n;i++)
printf("%d\t",RS[i]);
printf("\n");
printf("关键字参加的比较次数：%d,关键字的移动次数：%d\n",compare[1],move[1]);
printf("\n");

}

void InsertSort(int RS[],int n) //直接插入排序
{
int i,j;
for(i=2;i<=n;i++)
{
RS[0]=RS[i];
j=i-1;
move[2]++;
while(RS[0]<RS[j])
{
compare[2]++;
RS[j+1]=R