数据结构(C语言版)实验报告(内部排序算法比较).doc

(完整word版)数据结构(C语言版)实验报告(内部排序算法比较)
《数据结构与算法》实验报告

一、 需求分析
问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：
（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。数据测试：
二．概要设计
1. 程序所需的抽象数据类型的定义：
typedef int BOOL; //说明BOOL是int的别名
typedef struct StudentData { int num; //存放关键字
}
Data; typedef struct LinkList { int Length; //数组长度
Data Record[MAXSIZE]; //用数组存放所有的随机数
} LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组
void RandomNum() //随机生成函数
void InitLinkList(LinkList* L) //初始化链表
BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小
void Display(LinkList* L) //显示输出函数
void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) //希尔排序
void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) //快速排序
void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序
void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序
void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序
void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序
2 .各程序模块之间的层次（调用）关系：

二、 详细设计
typedef int BOOL; //定义标识符关键字BOOL别名为
int typedef struct StudentData //记录数据类型
{
int num; //定义关键字类型
}Data; //排序的记录数据类型定义
typedef struct LinkList //记录线性表
{
int Length; //定义表长
Data Record[MAXSIZE]; //表长记录最大值
}LinkList; //排序的记录线性表类型定义
int RandArray[MAXSIZE]; //定义随机数组类型及最大值
/******************随机生成函数********************/
void RandomNum()
{
int i; srand((int)time(NULL)); //用伪随机数程序产生伪随机数
for(i=0; i小于MAXSIZE; i++) RandArray[i]<=(int)rand(); 返回;
}
/*****************初始化链表**********************/
void InitLinkList(LinkList* L) //初始化链表
{
int i;
memset(L,0,sizeof(LinkList));
RandomNum();
for(i=0; i小于<MAXSIZE; i++)
L->Record[i].num<=RandArray[i]; L->Length<=i;
}
BOOL LT(int i, int j,int* CmpNum)
{
(*CmpNum)++; 若i<j) 则返回 TRUE; 否则返回 FALSE;
}
void Display(LinkList* L)
{
FILE* f; //定义一个文件指针f int i;
若打开文件的指令不为空则 //通过文件指针f打开文件为条件判断
{ //是否应该打开文件 输出“can't open file”; exit(0); }
for (i=0; i小于L->Length; i++)
fprintf(f,"%d\n",L->Record[i].num);
通过文件指针f关闭文件;
三、 调试分析
1. 调试过程中遇到的问题及经验体会:
在本次程序的编写和调试过程中，我曾多次修改代码，并根据调试显示的界面一次次调整代码。在调试成功之前，我的程序因为3个错误而无法运行，在经过完整并且仔细的检查后，发现3处错误分别是没有定义变量就直接套用、忘记加指针符号、忘记在嵌套语句后加大括号，这些看似不显眼的小问题却导致整个程序无法运行，所以我认为在编程过程中要及其严谨，尽量少犯或避免犯语法错误，保证代码的完整性。
2. 算法的时空分析：
1.稳定性比较： 插入排序、冒泡排序、简单选择排序及其他线形排序是稳定的； 希尔排序、快速排序、堆排序是不稳定的。
2.时间复杂性比较： 插入排序、冒泡排序、选择排序的时间复杂性为O(n2)； 其它非线形排序的时间复杂性为O(nlog2n)； 线形排序的时间复杂性为O(n)。
3.辅助空间的比较： 线形排序的辅助空间为O(n)，其它排序的辅助空间为O(1)。
4.其它比较： 插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了： 当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序； 当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。 当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。 当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。
四、 用户守则
1.可执行文件为：a.exe
2.为了界面更加友好特将背景颜色设计为黑色，字体为白色。
3.进入演示程序后即显示文本形式的用户界面，再按提示一步步完成：

五、 测试结果

测试结果及其分析：
通过本次程序的运行，得到数据：插入排序：比较的次数为25114496，交换的次数为25094525，花费的时间为1203ms；希尔排序：比较的次数为3834939，交换的次数为3782098，花费的时间为187ms；快速排序：比较的次数为153398，交换的次数为62804，花费的时间为0ms；堆排序：比较的次数为235273，交换的次数为124235，花费的时间为16ms；冒泡排序：比较的次数为49995000，交换的次数为27537172，花费的时间为2969ms；选择排序：比较的次数为50005000，交换的次数为9988，花费的时间为1656ms。 
算法效率是依据算法执行的时间来看的，从上面的数据来看，虽然插入排序的算法简洁，容易实现，但是从它执行的时间1203ms来看它的效率并不是很高，而且比较次数和交换次数都比较多，在这六种排序中效率是很底的；希尔排序的时间复杂度较直接排序低，在六种内部排序中效率居中；分析冒泡排序的效率，容易看出，若初始序列为“正序”序列，则只进行一趟排序，在排序过程中进行n-1次关键字的比较，反之，则需进行n-1趟排序，总的时间复杂度为O(n2)，在该程序中，冒泡排序所花费的时间为4360，是所有排序中花费最多的，可见效率是很底的。快速排序是对冒泡排序的一种改进，它所用的时间几乎为0，交换的比较的次数都比较少；堆排序仅次于快速排序，花费的时间只有16ms。 
由以上讨论可知，从时间上看，快速排序的平均性能都优于其他5种排序。 算法时间复杂度分析如下： 
1、直接插入排序： 当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的。最好情况是文件初态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初态为反序，相应的时间复杂度为O(n2)，算法的平均时间复杂度是O(n2)； 
2、选择排序是不稳定的，算法复杂度为O(n2)； 
3、快速排序是不稳定的主体算法时间运算量约 O(log2n) ，划分子区函数运算量约 O(n) ，所以总的时间复杂度为 O(nlog2n) ，它显然优于冒泡排序 O(n2)； 
4、希尔排序是不稳定的，算法复杂度是n1.25~1.6*n1.25； 
5、冒泡排序是稳定的，时间复杂度为O(n2)；
6、堆排序是不稳定的。

对各种表长和测试组数进行了测试，程序运行正常。分析实测得到的数值，6种排序算法的特点小结如下：

(1)若n较小（如n≤50），可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜；
(2)若文件初始状态基本有序（指正序），则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序； 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
六、 附录（源代码）
#include<stdio.h>
# include <stdlib.h>
# include <string.h>
# include <time.h>
# include <windows.h>
# include <winbase.h>
# define MAXSIZE 10000 //线性表中最多元素个数
#define TRUE 1
# define FALSE 0
typedef int BOOL; //定义标识符关键字BOOL别名为int typedef struct StudentData //记录数据类型
{
int num; //定义关键字类型
}Data; //排序的记录数据类型定义 typedef struct LinkList //记录线性表
{
int Length; //定义表长
Data Record[MAXSIZE]; //表长记录最大值
}LinkList; //排序的记录线性表类型定义 int RandArray[MAXSIZE]; //定义随机数组类型及最大值 /******************随机生成函数********************/
void RandomNum() //随机生成函数
{
int i;
srand((int)time(NULL)); //用伪随机数程序产生伪随机数 for(i=0; i<MAXSIZE; i++)
RandArray[i]=(int)rand(); return; }
/*****************初始化链表**********************/
void InitLinkList(LinkList* L) //初始化链表
{
int i;
memset(L,0,sizeof(LinkList));
RandomNum(); //调用随机函数
for(i=0; i<MAXSIZE; i++)
L->Record[i].num=RandArray[i]; L->Length=i;
}
BOOL LT(int i, int j, int* CmpNum) {
(*CmpNum)++;
if (i<j) return TRUE;
return FALSE;
}
void Display(LinkList* L)
{
FILE* f; //定义一个文件指针f int i;
if((f=fopen("SortRes.txt","w"))==NULL) //通过文件指针f打开文件为条件判断
{ //是否应该打开文件 printf("can't open file\n"); exit(0);
}
for (i=0; i<L->Length; i++)
fprintf(f,"%d\n",L->Record[i].num);
fclose(f); //通过文件指针f关闭文件
}
/***********冒泡排序*******************************/
void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum)
{ int i,j;
Data temp;
for (i=0; i<MAXSIZE-1;i++)
{
for(j=0;
j<MAXSIZE-i-1;j++) {
if(!LT(L->Record[j].num,L->Record[j+1].num,CmpNum))
{
(*ChgNum)++;
memcpy(&temp,&L->Record[j],sizeof(Data)); memcpy(&L->Record[j],&L->Record[j+1],sizeof(Data)); memcpy(&L->Record[j+1],&temp,sizeof(Data));
}
}
}
}
/*******选择排序*******************************/
int SelectMinKey(LinkList* L,int k,int* CmpNum)
{
int Min=k;
for ( k<L->Length; k++) {
if(!LT(L->Record[Min].num,L->Record[k].num,CmpNum))
Min=k;
}
return Min;
}
void SelSort(LinkList* L, int* CmpNum, int* ChgNum)
{
int i, j; Data temp;
for(i=0; i<L->Length; i++) {
j=SelectMinKey(L,i,CmpNum);
if(i!=j)
{
(*ChgNum)++;
memcpy(&temp,&L->Record[i],sizeof(Data)); memcpy(&L->Record[i],&L->Record[j],sizeof(Data)); memcpy(&L->Record[j],&temp,sizeof(Data));
}
}
}
/*************快速排序******************************/
int Partition (LinkList* L, int low, int high, int* CmpNum, int* ChgNum) {
Data Temp;
int PivotKey;
memcpy(&Temp,&L->Record[low],sizeof(Data)); PivotKey=L->Record[low].num;
while (low < high)
{
while (low<high && L->Record[high].num >= PivotKey)
{
high--;
(*CmpNum)++;
}
(*ChgNum)++; memcpy(&L->Record[low],&L->Record[high],sizeof(Data));
while (low<high && L->Record[low].num <= PivotKey)
{
low++;
(*CmpNum)++;
}
(*ChgNum)++; memcpy(&L->Record[high],&L->Record[low],sizeof(Data));
}
memcpy(&L->Record[low],&Temp,sizeof(Data));
return low;
}
void QSort (LinkList* L, int low, int high, int* CmpNum, int* ChgNum) {
int PivotLoc=0;
if (low < high)
{
PivotLoc=Partition(L,low,high,CmpNum,ChgNum); QSort(L,low,PivotLoc-1,CmpNum,ChgNum); QSort(L,PivotLoc+1,high,CmpNum,ChgNum); }
}
void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) {
QSort(L,0,L->Length-1,CmpNum,ChgNum);
}
/*********************希尔排序*************************/ void ShellInsert(LinkList* L,int dk, int* CmpNum, int* ChgNum)
{
int i, j; Data Temp; for(i=dk; i<L->Length;i++) {
if( LT(L->Record[i].num, L->Record[i-dk].num, CmpNum) ) {
memcpy(&Temp,&L->Record[i],sizeof(Data));
for(j=i-dk; j>=0 && LT(Temp.num, L->Record[j].num, CmpNum) j-=dk)
{
(*ChgNum)++; memcpy(&L->Record[j+dk],&L->Record[j],sizeof(Data));
}
memcpy(&L->Record[j+dk],&Temp,sizeof(Data));
}
}
}
void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum)
{
int k; for (k=0; k<t; k++) ShellInsert(L,dlta[k],CmpNum,ChgNum); } /************堆排序******************************/
void HeapAdjust (LinkList* L,int s, int m, int* CmpNum, int* ChgNum)
{
Data Temp;
int j=0; s++;
memcpy(&Temp,&L->Record[s-1],sizeof(Data));
for (j=2*s; j<=m j*=2)
{
if(j<m && LT(L->Record[j-1].num,L->Record[j].num,CmpNum))
++j;
if(!LT(Temp.num,L->Record[j-1].num,CmpNum))
break;
(*ChgNum)++; memcpy(&L->Record[s-1],&L->Record[j-1],sizeof(Data));
s=j;
}
memcpy(&L->Record[s-1],&Temp,sizeof(Data)); }
void HeapSort (LinkList* L, int* CmpNum, int* ChgNum)
{
int i=0;
Data Temp;
for (i=L->Length/2-1; i>=0; i--)
HeapAdjust(L,i,L->Length,CmpNum,ChgNum);
for (i=L->Length; i>1; i--)
{
memcpy(&Temp,&L->Record[0],sizeof(Data));
(*ChgNum)++;
memcpy(&L->Record[0],&L->Record[i-1],sizeof(Data)); memcpy(&L->Record[i-1],&Temp,sizeof(Data)); HeapAdjust(L,0,i-1,CmpNum,ChgNum);
}
}
/****************比较所有排序******************************/
void Compare(LinkList* L,int* CmpNum, int* ChgNum) {
int TempTime,i;
int SpendTime;
int dlta[3]={7,3,1};
int Indata[1]={1};
TempTime=(int)GetTickCount(); ShellSort(L,Indata,1,&CmpNum[0],&ChgNum[0]); SpendTime=(int)GetTickCount()-TempTime; printf("\n\t====================================================="); printf("\n\n\t插入排序:");
printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间 =%dms",CmpNum[0],ChgNum[0],SpendTime);
for(i=0; i<MAXSIZE; i++)
L->Record[i].num=RandArray[i]; //随机数列复位 TempTime=(int)GetTickCount();
ShellSort(L, dlta, 3,&CmpNum[1],&ChgNum[1]);
SpendTime=(int)GetTickCount()-TempTime;
printf("\n\n\t希尔排序:");
printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间 =%dms",CmpNum[1],ChgNum[1],SpendTime);
for(i=0; i<MAXSIZE; i++)
L->Record[i].num=RandArray[i]; //随机数列复位
TempTime=(int)GetTickCount();
QuickSort(L,&CmpNum[2],&ChgNum[2]); SpendTime=(int)GetTickCount()-TempTime;
printf("\n\n\t快速排序:");
printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间 =%dms",CmpNum[2],ChgNum[2],SpendTime);
for(i=0; i<MAXSIZE; i++)
L->Record[i].num=RandArray[i]; //随机数列复位 TempTime=(int)GetTickCount();
HeapSort(L,&CmpNum[3],&ChgNum[3]); SpendTime=(int)GetTickCount()-TempTime;
printf("\n\n\t堆排序:");
printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间 =%dms",CmpNum[3],ChgNum[3],SpendTime);
for(i=0; i<MAXSIZE; i++) L->Record[i].num=RandArray[i]; //随机数列复位 TempTime=(int)GetTickCount();
BubbleSort(L,&CmpNum[4],&ChgNum[4]); SpendTime=(int)GetTickCount()-TempTime;
printf("\n\n\t冒泡排序:");
printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间 =%dms",CmpNum[4],ChgNum[4],SpendTime);
for(i=0; i<MAXSIZE; i++) L->Record[i].num=RandArray[i];
//随机数列复位
TempTime=(int)GetTickCount();
SelSort(L,&CmpNum[5],&ChgNum[5]); SpendTime=(int)GetTickCount()-TempTime;
printf("\n\n\t选择排序:");
printf("\n\t比较的次数=%d\t交换的次数=%d\t所用的时间 =%dms",CmpNum[5],ChgNum[5],SpendTime); printf("\n\t====================================================="); }
/***************主函数*******************************/
void main() { int select=0;
int dlta[3]={7,3,1}; int Indata[1]={1};
int CmpNum[6],ChgNum[6]; //CnpNum数组时比较次数，ChgNum是交换次数
int SpendTime=0;
LinkList L; InitLinkList(&L);
memset(CmpNum,0,sizeof(CmpNum)); memset(ChgNum,0,sizeof(ChgNum)); printf("\n\n\t\t******************************************\n"); printf("\t\t 数据结构课程设计\n\n");
printf("\t\t ——内部排序算法的比较\n\n");
printf("\t\tPlese press enter to continue...\n"); printf("\t\t******************************************");
getchar(); system("cls.exe");
printf("\n\t正在计算，请稍等....."); Compare(&L,CmpNum,ChgNum);//比较所有排序
Display(&L); printf("\n\n\t比较结束, 请按回车键!\n");
getchar();
getchar();
}