数据结构与算法》实验报告一、需求分析问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。

试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。

基本要求：（l ）对以下 6 种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。

（2 ）待排序表的表长不小于100000 ；其中的数据要用伪随机数程序产生；至少要用 5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为 3 次移动）。

（ 3 ）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。

数据测试：二．概要设计1. 程序所需的抽象数据类型的定义：typedef int BOOL;typedef struct StudentData { }Data; typedef struct LinkList { Data Record[MAXSIZE]; int num; // 存放关键字int Length; // 数组长度// 用数组存放所有的随机数// 说明BOOL 是int 的别名} LinkList int RandArray[MAXSIZE]; // 定义长度为MAXSIZE 的随机数组void RandomNum() // 随机生成函数void InitLinkList(LinkList* L) // 初始化链表// 比较所有排序2 . 各程序模块之间的层次（调用）关系：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, // 快速排序voidHeapSort(LinkList*L, // 堆排序void BubbleSort(LinkList* L, // 冒泡排序void SelSort(LinkList* L, // 选择排序int* CmpNum, int* ChgNum)int* CmpNum, int* ChgNum)int* CmpNum, int* ChgNum)*CmpNum, int* ChgNum)void Compare(LinkList*L,int* CmpNum, int* ChgNum)// 希尔排序//定义标识符关键字BOOL别名为//记录数据类型//定义关键字类型//排序的记录数据类型定义typedef struct Lin kList //记录线性表详细设计typedef int BOOL;int typedef struct Stude ntData{int num;}Data;// 定义表长 // 表长记录最大值// 排序的记录线性表类型定义// 定义随机数组类型及最大值void RandomNum(){int i; srand((int)time(NULL)); for(i=0; i 小于 MAXSIZE; i++)}/*****************初始化链表 **********************/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){void Display(LinkList* L){FILE* f;// 定义一个文件指针 f int i;****************随机生成函数 ******************int Length;Data Record[MAXSIZE]; }LinkList;int RandArray[MAXSIZE];// 用伪随机数程序产生伪随机数RandArray[i]<=(int)rand();返回 ;(*CmpNum)++; 若i<j) 则返回TRUE; 否则返回FALSE;若打开文件的指令不为空则// 通过文件指针 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) ；其它非线形排序的时间复杂性为0( nlog2 n) 线形排序的时间复杂性为0(n)。

3. 辅助空间的比较：线形排序的辅助空间为0(n)，其它排序的辅助空间为0(1)。

4. 其它比较：插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。

反而在这种情况下，快速排序反而慢了：当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序；当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

四、用户守则1.可执行文件为：a.exe2. 为了界面更加友好特将背景颜色设计为黑色，字体为白色。

3.进入演示程序后即显示文本形式的用户界面，再按提示一步步完成:测试结果及其分析：通过本次程序的运行，得到数据：插入排序：比较的次数为25114496，交换的次数为25094525，花费的时间为1203ms ；希尔排序：比较的次数为3834939 ，交换的次数为3782098 ，花费五、测试结果交挣一旳次粧P 沖U 刖日交唤的灰数活冊站冒泡交骐的次数■抽■・所用的吋间-ltS6»所埔的时间-2M5«£比较结束，谓按回车蜒所坤的时怛卜1触U正在W.谓趟爭女帳沟农最-EW745E5 .交护覘冼駅吨了鬧相挖所粕的对间"197"5 所馬曲时问-倨即忸 肝用的时间-etas的时间为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) ，最坏情况是文件初态为反序，相应的时间复杂度为0(n2)，算法的平均时间复杂度是0(n2);2、选择排序是不稳定的，算法复杂度为0(n2);3、快速排序是不稳定的主体算法时间运算量约O(log2 n)，划分子区函数运算量约0(n)，所以总的时间复杂度为0(nlog2n)，它显然优于冒泡排序0(n2)；4、希尔排序是不稳定的，算法复杂度是n1.25~1.6* n1.25 ；5、冒泡排序是稳定的，时间复杂度为0(n2)；6、堆排序是不稳定的。

对各种表长和测试组数进行了测试，程序运行正常。

分析实测得到的数值，6种排序算法的特点小结如下：(1)若较小(如<),可采用直接插入或直接选择排序。

当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜；(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；⑶若n较大，则应采用时间复杂度为0(nign)的排序方法：快速排序、堆排序或归并排序；快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。

这两种排序都是不稳定的。

附录（源代码）#inciude<stdio.h># inciude <stdiib.h># inciude <string.h># inciude <time.h># inciude <windows.h># inciude <winbase.h># define MAXSIZE 10000 #define TRUE 1# define FALSE 0 typedef int B00L; int typedef struct StudentData{int num;}Data;// 线性表中最多元素个数// 定义标识符关键字B00L 别名为// 记录数据类型// 定义关键字类型// 排序的记录数据类型定、▲义 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];及最大值 / ******************随机生成函数 ************************************* 初始化链表 ********************** // 记录线性表 // 随机生成函数// 用伪随机数程序产生伪随机return; }// 初始化链表// 调用随机函数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; int i;if((f=fopen("SortRes.txt","w"))==NULL) 打开文件为条件判断{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;// 定义一个文件指针 f// 通过文件指针 f// 是否应该打开文件***********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; 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<mLT(L->Record[j-1].num,L->Record[j].num,CmpNum)) ++j;if(!LT(Temp.num,L->Record[j-1].num,CmpNum))break;k++) 堆排序&&(*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("\t\t 数据结构课程设计 \n\n");getchar(); system("cls.exe");Compare(&L,CmpNum,ChgNum);//Display(&L); printf("\n\n\tgetchar();getchar();printf("\n\n\t\t ****************************************** \n");printf("\t\t内部排序算法的比较 \n\n"); printf("\t\tPlese press enter to continue...\n"); printf("\t\t** ****************************************H );printf("\n\t 正在计算请稍等 ); 比较所有排序 比较结束 , 请按回车键 !\n");THANKS !!!致力为企业和个人提供合同协议，策划案计划书，学习课件等等打造全网一站式需求欢迎您的下载，资料仅供参考-可编辑修改-。