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

数据结构(C语言版)实验报告 (内部排序算法比较)当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下，宜用归并排序当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序用户守则1.可执行文件为：a.ee2.为了界面更加友好特将背景颜色设计为黑色，字体为白色3.进入演示程序后即显示文本形式的用户界面，再按提示一步步完成：测试结果测试结果及其分析^p ： 通过本次程序的运行，得到数据：插入排序：比较的次数交换的次数花费的时间为1203ms；希尔排序：比较的次数为3834939，交换的次数为3782098，花费的时间为187ms；快速排序：比较的次数为153398，交换的次数为62804，花费的时间为0ms；堆排序：比较的次数为235273，交换的次数为124235，花费的时间为16ms；冒泡排序：比较的次数交换的次数花费的时间为2969ms；选择排序：比较的次数交换的次数为9988，花费的时间为1656ms算法效率是依据算法执行的时间来看的，从上面的数据来看，虽然插入排序的算法简洁，容易实现，但是从它执行的时间1203ms来看它的效率并不是很高，而且比较次数和交换次数都比较多，在这六种排序中效率是很底的；希尔排序的时间复杂度较直接排序低，在六种内部排序中效率居中；分析^p 冒泡排序的效率，容易看出，若初始序列为“正序”序列，则只进行一趟排序，在排序过程中进行n-1次关键字的比较，反之，则需进行n-1趟排序，总的时间复杂度为O(n2)，在该程序中，冒泡排序所花费的时间为4360，是所有排序中花费最多的，可见效率是很底的。

快速排序是对冒泡排序的一种改进，它所用的时间几乎为0，交换的比较的次数都比较少；堆排序仅次于快速排序，花费的时间只有16ms由以上讨论可知，从时间上看，快速排序的平均性能都优于其他5种排序算法时间复杂度分析^p 如下：?1、直接插入排序：?当文件的初始状态不同时，直接插入排序所耗费的时间是有很大差异的最好情况是文件初态为正序，此时算法的时间复杂度为O(n)，最坏情况是文件初态为反序，相应的时间复杂度为O(n2)，算法的平均时间复杂度是O(n2)；?2、选择排序是不稳定的，算法复杂度为O(n2)；?3、快速排序是不稳定的主体算法时间运算量约?O(log2n)?，划分子区函数运算量约?O(n)?，所以总的时间复杂度为?O(nlog2n)?，它显然优于冒泡排序?O(n2)；?4、希尔排序是不稳定的，算法复杂度是n1.25~1.6n1.25；?5、冒泡排序是稳定的，时间复杂度为O(n2)；6、堆排序是不稳定的对各种表长和测试组数进行了测试，程序运行正常分析^p 实测得到的数值，6种排序算法的特点小结如下：(1)若n较小（如n≤50），可采用直接插入或直接选择排序当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜； (2)若文件初始状态基本有序（指正序），则应选用直接插人、冒泡或随机的快速排序为宜； (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序； 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。

这两种排序都是不稳定的附录（代码）#include# include # include # include # include # include # define MASIZE 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[MASIZE]; //表长记录最大值 }LinkList; //排序的记录线性表类型定义 int RandArray[MASIZE]; //定义随机数组类型及最大值 /随机生成函数/ void RandomNum //随机生成函数 { int i; srand((int)time(NULL)); //用伪随机数程序产生伪随机数 for(i=0; iRecord[i].num=RandArray[i]; L->Length=i; } BOOL LT(int i, int j, intCmpNum) { (CmpNum)++; if (iLength; i++) fprintf(f,“d\n”,L->Record[i].num); fclose(f); //通过文件指针f关闭文件 } /冒泡排序/ void BubbleSort(LinkListL, intCmpNum, intChgNum) { int i,j; Data temp; for (i=0; iRecord[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(LinkListL,int k,intCmpNum){ int Min=k;for ( kLength; k++) { if(!LT(L->Record[Min].num,L->Record[k].num,CmpNum)) Min=k; } return Min; } void SelSort(LinkListL, intCmpNum, intChgNum) { int i, j; Data temp; for(i=0; iLength; 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 (LinkListL, int low, int high, intCmpNum, intChgNum) { Data Temp;int PivotKey; memcpy(Temp,L->Record[low],sizeof(Data)); PivotKey=L->Record[low].num; while (low Record[high].num >= PivotKey) { high--; (CmpNum)++; } (ChgNum)++; memcpy(L->Record[low],L->Record[high],sizeof(Data));while (lowRecord[low].num Record[high],L->Record[low],sizeof(Data)); } memcpy(L->Record[low],Temp,sizeof(Data)); return low; } void QSort (LinkListL, int low, int high, intCmpNum, intChgNum) { int PivotLoc=0; if (low Length-1,CmpNum,ChgNum); } /希尔排序/ void ShellInsert(LinkListL,int dk, intCmpNum, intChgNum) { int i, j; Data Temp; for(i=dk; iLength;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(LinkListL, int dlta[], int t,intCmpNum, intChgNum){ int k; for (k=0; kRecord[s-1],sizeof(Data)); for (j=2s; jRecord[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 (LinkListL, intCmpNum, intChgNum) { 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-。