《内部排序算法比较毕业设计（论文）word格式.doc》由会员分享，可在线阅读，更多相关《内部排序算法比较毕业设计（论文）word格式.doc（19页珍藏版）》请在三一办公上搜索。
1、内部排序算法的比较一 目的利用数据结构课程的相关知识完成各种内部排序算法的比较，计算出每种内部排序算法的关键字比较次数，移动次数几其时间复杂度。利用C/C+语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。二 需求分析1、基本要求(1) 对以下10种内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序、折半插入排序、二路插入排序、归并排序
2、、基数排序。(2) 待排序表的表长不小于100；其中的数据要用伪随机数产生器产生；至少要用5组不同的输入数据做比较；比较的指标为关键字参加的比较次数和关键字的移动次数（关键字交换为3次移动）。(3) 针对不同的输入表长做试验，观测检查两个指标相对表长的变换情况。(4) 随机产生的数据保存到文件input.txt中，将各个算法的关键字比较次数和关键字移动次数的比较分析结果，显示输出到屏幕，并保存到Out.txt文件中。2、数据测试测试数据由系统随机数生成器生成，并且保存到文件件input.txt中。三 概要设计1、获取随机数void InitList(SqList &H,SqList L)，动态
3、法分配数组，以存储关键字。void GetKey(SqList &L,int n)， 产生随机数，即产生关键字。2、始终内部排序法函数：InsertSort(H1,w)，直接插入排序函数。BInsertsort(H6,w)，折半插入排序函数。P2_InsertSort(H7,w)，2_路插入排序函数。Shellsort(H2,dlta,7,w)，希尔排序函数。BubbleSort(H3,w)冒泡排序函数。QuickSort(H4,w)，快速排序函数。SelectSort(H5,w)，简单选择排序函数。HeapSort(H,w)，堆排序函数MergeSort(H8,w),归并排序函数。Radix
4、Sort_ascend(H,P)，基数排序函数。3、元素移动次数与比较次数： 当两个元素值进行交换时，元素移动次数为三。两元素每比较一次，move值加一。4、程序模块1） 主程序模块void main() /初始化； / 开辟空间； do /接受命令； /处理命令；while(命令=“继续”)；2） 随机模块随机产生数组和可用数据文档3） 十种内部排序函数4） 函数的调用关系图反映程序的层次结构：ShellInsertQuickSort() P2_InsertSort( )GetKey( )Main()Paixu( )InsertSort( )Binsertsort( )RadixSort_a
5、scend( )InitList( )BubbleSort( )SelectSort()()HeapSort()MergeSort()ShellsortdistributeCollect_ascendsucc_ascendMsort()Msort()Merge()HeapAdjusHeapAdjustQSortQSortPartition四 详细设计1、头文件定义： #include#include#include#include#include#include#include#include/int MAXSIZE=100,200,500,1000;/数组递增表#define LT(a,b)
6、 (a)(b)/#define Radix 10typedef int KeyType;int dlta7=33,17,9,5,3,2,1;/希尔增量数组int compare=0,move=0; /比较，移动次数，全局变量double times,start,end;2、存储结构描述：typedef struct KeyType key; /关键字项RedType;/链表存储typedef struct RedType *r; /数据元素存储基地址，动态分配数组 int lengh; /数组长度SqList;/动态数组以下为基数排序存储结构#define maxspace 10000type
7、def structint key;int next;SLCell;typedef structSLCell rmaxspace;int keynum;int recnum;SList;3、主函数及其他子函数描述：int main() /主程序 /定义变量do 提示菜单，按要求输入，选择操作。 Case 1：GetKey()，产生随机数，即关键字。H1=paixu()。Case 2:/ 待排序数组逆序 H1=paixu()。Case 3:/ 移动次数及比较次数赋为0。H1=paixu()。 whilevoid GetKey() L.r=(RedType*)malloc(sizeof(RedTy
8、pe)*n)/动态分配数组大小 /调用随机数生成函数，根据main函数中输入的变量，确定产生元素个数。SqList paixu() /定义变量 InitList(),动态分配数组大小,等到每种排序的初始数据，使得每种排序的初始数据都相同。 /分别调用十种内部排序算法的函数，及其时间函数。并将排序过程中的移动次数，关键字比较次数，还有所需时间输出。void InitList() for(int i=0;i=L.ri+1 The swap(L.ri,L.ri+1),compare+=3 Else i+void BInsertsort(SqList &L,int c,int mo) /折半插入排序。
9、 for i=high+1;j-) L.rj+1=L.rj/进行元素交换void P2_InsertSort(SqList &L,int m,int n) /2_路插入排序 d=(RedType*)malloc(L.lengh*sizeof(RedType) / 生成L.length个记录的临时空间for(i=2;i=L.lengh;+i) / 依次将L的第2个最后1个记录插入d中 compare+; if(L.ri.keydfinal.key) / 待插记录大于d中最大值，插到dfinal之后(不需移动d数组的元素) dfinal=L.ri; else / 待插记录大于d中最小值，小于d中最
10、大值，插到d的中间(需要移动d数组的元素)。 j=final+; / 移动d的尾部元素以便按序插入记录 void Shellsort(SqList &L,int dlta,int t,int c,int mo) /希尔排序 ShellInsert(L,dltak) /一趟增量为dltak的插入排序void ShellInsert(SqList &L,int dk) /对顺序表L做一趟希尔插入排序，r0做暂存单元，当j0<(L.r0.key,L.rj.key); L.rj+dk=L.r0;/插入void BubbleSort(SqList &L,int m,int n) /起泡法排序 for
11、(i=1;iL.lengh;i+) for(j=1;jL.rj+1.key) Swap（L.rj.key，.rj+1.key）void QuickSort(SqList &L,int m,int n) /对顺序表L做快速排序。 QSort(L,1,L.lengh)void QSort(SqList &L,int low,int high) /对顺序表中的子序列L.rlow.high做快速排序 If lowhigh The pivotloc=Partition(L,low,high);/将L.rlow.high一分为二 QSort(L,low,pivotloc-1);/对低子表递归排序，pivo
12、tloc是枢轴位置 QSort(L,pivotloc+1,high);/对高子表递归排序int Partition(SqList &L,int low,int high) /交换顺序表L中子表rlow.high的记录，枢轴记录到位并返回所在位置，此时在它之前（后）的记录位置均不大（小）于它.while(lowhigh)/从表的两端交替地向中间扫描 while(low=pivotkey) -high; L.rlow=L.rhigh;/将比枢轴记录小的记录移动到低端 while(lowhigh&L.rlow.key=pivotkey) +low; L.rhigh=L.rlow;/将比枢轴记录大的记
13、录移动到高端 L.rlow=L.r0;/枢轴记录到位 return low;/返回枢轴位置 void SelectSort(SqList &L,int m,int n)/对顺序表L做简单选择排序for(i=1;iL.lengh;i+)/选择第i小的记录，并交换到位 for(k=i+1;k=L.lengh;k+)/在L.ri.L.lengh中选择key最小的记录 if L.rk.key1;-i)swap（H.r1.key，H.ri.key）/堆顶记录和当前未排子序列中最后一个记录相交换。HeapAdjust(H,1,i-1);/将H. rl . i - 1 重新调整为大/小顶堆void Heap
14、Adjust(HeapType &H,int s,int m) / H.rs . m中除H.rs.key外均满足堆的定义/ 调整H.rs的关键字，使H.rs . m成为一个小顶堆void MergeSort(SqList &L,int m,int n) /归并排序 MSort(L,L,1,L.lengh)void MSort(RcdType SR,RcdType TR1,int s, int t) /对待排序数列进行分划 if(s=t) TR1.rs.key=SR.rt.key; Else m=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); M
15、erge(TR2,TR1,s,m,t); void Merge(RcdType SR,RcdType &TR,int i,int m,int n) /对分划好的数组进行归并 for(j=m+1,k=i;i=m&j=n;+k) if(SR.ri.keyr,i,f,e) Collect_ascend(H,L-r,f,e)void distribute(SqList &H,SLCell *r,int i,int *f,int *e) for(p=r0.next;p;p=rp.next)if(!fj) fj=p; ej=p;else rej.next=p; ej=p;/将P所指的节点插入第J个子表中
16、void Collect_ascend(SqList &H,SLCell *r,int *f,int *e) /按照关键字将各个子表依次连接为一个链表 while(j10) for(j=succ_ascend(j,f);j9 & (!fj);j=succ_ascend(j,f) /找到下一个非空字表 if(fj&j10) rt.next =fj; t= ej; /连接两个非空字表int succ_ascend(int j,int *f) while(t=9)if(ft!=0) return t;else t+;return 10;4、程序主流程图 开始定义变量输出菜单，提示输入i=？ i=2i
17、=1或i=3i=1 i=3GetKey()将数据逆序排列Paixu()初始化数组，得到十组相同数据调用十种排序算法，并将结果输出按提示输入chCh=?结束Ch!=y/YCh=y/Y五 调试分析1.在写本程序之前，首先要熟悉每种排序算法的思想，了解每种排序法在最好最坏及平均情况下的时间复杂度、元素比较次数及元素移动次数。2.在了解了每种排序算法的思想后，应注意，其实本程序虽说是三种要求排序，但其实三类要求排序的代码段都是相同的，每种排序都只用一种算法就可以，特别注意逆序排序，不是直接调用第一次排序的结果，而是调用第一次结果的逆序数列，为逆序排序的初始数据。3.基数排序的存储结构比较特殊，需要一特
18、别定义一些新的存储结构，另外需要定义一个基数量maxspace。4，元素移动次数上要小心，当进行两个元素交换操作时，引入了一个辅助的空间，即哨兵，当进行两个元素交换操作时，需要三次赋值操作，所以，当两个元素交换时，元素移动次数为3而不是2。六 测试结果测试结果如下：1.当初始操作时，得到随机数据，写入文件“intput.txt”: 将这组数据按照要求排序，得到的三组排序结果如图：1）.随机数排序结果： 此时，排好序的数据输出到“output1.txt”中，结果如图： 2.调用第一组排序的结果，进行第二次排序，逆排序排序结果如图： 输出的排序结果为：输出文档中的数据为：3.进行第三次排序，调用第
19、二次排序的结果，屏幕输出结果为：输出文档中的数据与上两步中的结果相同。七 用户使用说明1.本程序的运行环境为VC2. 运行后，在界面上会有一个选择菜单如图:根据提示输入1、2、或3（要求第一次运行输入时输入为1，要产生随机数）。3.再输入“1”的情况下： 按照提示输入，一般输入数据为100的整数倍。4.再输入100的情况下：按提示输入，进行操作。5.输入Y以后： 此时，可按提示进行输入，可执行2.、3操作。6、在选择2操作命令后：按提示输入。7、再输入Y后，菜单界面如同第步，其他键（除enter键）则结束操作。8、再输入Y的情况下，按提示输入，选择3操作的结果如图：可进行循环操作，也可以在此基
20、础上再次进行2、3操作，操作结果不变。八 课程设计总结1. 完成这个课程设计达到了实验的目的，加强了对各种内部排序法的的了解，同时提高了对这部分知识的运用能力，当然编程的能力也有所历练和提高。2. 由于本程序用到文件的输入输出，这让以前经常忽视文件应用知识的我掌握了文件的运用。同时在完成此程序的过程中，学习了随机函数，自觉丰富了知识，学到很多，以后对于编程应该很有用。3. 一级指针，二级指针，指针函数以及指向函数的指针及数组的运用，让我更加熟悉这些知识，不仅是个复习已学知识的机会，也是个重新学习的机会4. 写程序就会出错，出错就要改错，在成功完成实验的过程中，改错能力。也有所提高，改错也是个熟练运用知识的的过程，也是个相当重要的个人能力。5. 对于界面的控制部分，其实是每个程序员都要很慎重考虑的部分，好的界面有助于用户更好操作，所以实现一个好的易操作的界面环境也是我们需要好好锻炼和学习的，在不断学习和编程中提高能力，同时也养成好的编程习惯。
