2022年结构各种排序算法课程分析方案.docx

《2022年结构各种排序算法课程分析方案.docx》由会员分享，可在线阅读，更多相关《2022年结构各种排序算法课程分析方案.docx（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 课程设计题目 排序算法实现将比较滁 州 学 院课程设计报告课程名称：数据结构设计题目 ：排序算法实现及比较系别：运算机信息工程学院专业：运算机科学与技术组别：第*组起止日期 : 12 年 5 月 1 日 12 年 6 月 1 日指导老师 :* 运算机与信息工程学院二一二年制课程设计任务书1 / 32 名师归纳总结 - - - - - - -第 1 页,共 32 页精选学习资料 - - - - - - - - - 组长* 学号20* 班级* 系别运算机与信息工程学院专业* 运算机科学与技术组员* 指导老师加深对常见排序算法懂得 课程设计目的 通过

2、程序比较常见算法优越性 熟识加深对数据结构的明白及熟识课程设计所需环境 Windows xp；VC+6.0 实现常见排序算法程序化课程设计任务要求测试程序比较算法优越性 明白常见算法的实际应用课程设计工作进度方案序号起止日期工 作 内 容年分工情形1 分析试验类容编写报告2 分工3 算法改编成程序将子程序合并及调试4 数据测试及记录5 指导老师签字：月日系教研室）审核看法：系教研室）主任签字：年月日目录1.引言 3 2.需求分析 4 3.具体设计 4 3.1 直接插入排序 4 3.2 折半排序 4 3.3 希尔排序 5 3.4 简洁挑选排序 6 2 / 32 名师归纳总结 - - - - -

3、- -第 2 页,共 32 页精选学习资料 - - - - - - - - - 3.5 堆排序 6 3.6 归并排序 7 3.7 冒泡排序 9 4.调试 10 5.调试及检验 10 5.1 直接插入排序 10 5.2 折半插入排序 11 5.3 希尔排序 11 5.4 简洁挑选排序 12 5.5 堆排序 12 5.6 归并排序 13 5.7 冒泡排序 14 6.测试与比较 15 6.1 调试步骤 15 6.2 结论 15 7.试验心得与分析 15 8.附录 16 8.1 直接插入排序 16 8.2 折半插入排序 17 8.3 希尔排序 19 8.4 简洁挑选排序 21 8.5 堆排序 23 8

4、.6 归并排序 25 8.7 冒泡排序 28 8.8 主程序 30 1.引言相伴着社会的进展,数据也变得越来越巨大；如何将巨大的数据进行很好的排序,使用户更加方 便的查找资料,成了一件越来越重要的问题；对于程序员来说,这将是一个挑战；常常查找资料的伴侣都会知道,面对海量的资料,假如其查找的资料没有进行排序,那么其查找 资料将会是一件特别痛楚的事情；针对这一问题,我们自此通过一个课程设计来解决它；理论上排序算法有许多种,不过本课程设计只涉及到七种算法；这七种算法共包括：直接插入排 序,折半插入排序,希尔排序,简洁挑选排序,堆排序,归并排序,冒泡排序；本课程设计通过对这七种算法的运行情形进行对比,

5、挑选最优秀的算法来供应应用户；期望通过 我们的努力能给用户解决一些问题,带来一些便利；3 / 32 名师归纳总结 - - - - - - -第 3 页,共 32 页精选学习资料 - - - - - - - - - 2.需求分析本课程题目是排序算法的实现,由于各方面的缘由,本课程设计一共要设计七种排序算法；这七种算法共包括：直接插入排序,折半插入排序,希尔排序,简洁挑选排序,堆排序,归并排序,冒泡排序；七种排序各有独到之处,因此我们要通过各种调试分析来比较其优劣长短；为了小组分工的便利,我们特意把子函数写成Header File 文件；这样操作不仅可以使小组分工更加简洁明白,仍可以便利子函数的调

6、用,更可以使写主函数时一目了然；为了运行时的便利,我们将七种排序方法进行编号,其中1 为直接插入排序,2 为折半插入排序,3 为希尔排序, 4 为简洁挑选排序,5 为堆排序, 6 为归并排序, 7 为冒泡排序；通过这七种选项,可以让用户简洁明白的去挑选使用哪一种排序方法；本课程就是通过对 5 组占用内存大小不同的数据调试来测试这七种算法运行的时间长短,从中选 择面对不同大小的文件时,哪一种算法更为快捷；软件环境本课程设计所用操作系统为Windows-XP操作系统,所使用的软件为Microsoft Visual C+ 6.0 ；3.具体设计3.1 直接插入排序 算法思想：直接插入排序是一种最简洁

7、的排序方法,它的基本操作是将一个记录插入到一个已排好序的有序表中,从而得到一个新的、记录数增一的有序表；在自i-1 起往前搜寻的过程中,可以同时后移记录；整个排序过程为进行 n-1 趟插入,即：先将序列中的第一个记录看成是一个有序的 子序列,然后从其次个记录起逐个进行插入,直至整个序列变成按关键字非递减有序序列为止；程序实现及核心代码的注释：for i = 1 ； i forj=0 ；j ifr.basei temp = r.basei； / 储存待插入记录 fori= i ；i j ； -i r.basei = r.basei-1 ； /记录后移 r.basej = temp； / 插入到正

8、确的为位置 r.baser.length =0 ；3.2折半排序 算法思想：由于折半插入排序的基本操作是在一个有序表中进行查找和插入,这个“查找 ”操作可 利用折半查找来实现,由此进行的插入排序称之为折半插入排序；折半插入排序所需附加储备空间4 / 32 名师归纳总结 - - - - - - -第 4 页,共 32 页精选学习资料 - - - - - - - - - 和直接插入排序相同,从时间上比较,这般插入排序仅削减了关键字间的比较次数,而记录的移动 次数 不变；因此,这般插入排序的时间复杂度仍为 O / 对次序表作折半插入排序 for i = 1 ； i temp=r.basei ； /将

9、 r.basei寄存在 temp 中 low=0 ；high=i-1 ；while low /在 baselow 到 keyhigh 中折半查找有序插入的位置 m = low+high/2 ； /折半 if temp high = m-1 ； /插入低半区 else low = m+1 ； /插入高半区 for j=i-1 ； j=high+1 ； -j r.basej+1= r.basej ； /记录后移 r.basehigh+1=temp ； /插入 3.3 希尔排序 算法思想：先将整个待排记录序列分割成为如干子序列分别进行直接插入排序,待整个序列中的 记录 “基本有序 ”时,再对全体记录

10、进行一次直接插入排序；其中,子序列的构成不是简洁的“ 逐段分割 ” ,而是将分隔某个“ 增量 ” 的记录组成一个子序列；程序实现及核心代码的注释：fork = 0 ； k m = 10 - k ；for i = m ； i ifr.basei 5 / 32 名师归纳总结 - - - - - - -第 5 页,共 32 页精选学习资料 - - - - - - - - - temp = r.basei； / 储存待插记录 forj = i - m ； j = 0 & temp r.base j + m = r.basej ； /记录后移,查找插入位置 r.base j + m = temp ； /

11、 插入 3.4简洁挑选排序 算法思想：在要排序的一组数中,选出最小的一个数与第一个位置的数交换；然后在剩下的数当 中再找最小的与其次个位置的数交换,如此循环到倒数其次个数和最终一个数比较为止；程序实现及核心代码的注释：for i = 0 ； i /i 为排好序的数的下标,依次往后存放排 /好序的数 temp=r.basei； / 将待放入排好序的数的下标的数储存 for j = i,m = j +1 ； m / 找出未排序的数中最小的数的循环；ifr.basej r.basem j = m ；r.basei = r.basej ； / 把下标为 j 的数与 i 数互换；r.basej = te

12、mp； 3.5堆排序 算法思想：堆排序只需要一个记录大小的帮助空间,每个待排序的记录仅占有一个储备空间；将 序列所储备的元素 AN 看做是一棵完全二叉树的储备结构,就堆实质上是满意如下性质的完全二叉树：树中任一非叶结点的元素均不大于 间复杂度为 ONlogN ；程序实现及核心代码的注释：void dpFILE *fp 或不小于 其左右孩子 如存在 结点的元素；算法的平均时fori = r.length / 2 ；i = 1 ； -i / 把 r.base1.r.length 建成大顶堆 HeapAdjustr.base,i,r.length ； fori = r.length ；i = 2 ；

13、 -i temp = r.base1； r.base1 = r.basei；r.basei = temp；6 / 32 名师归纳总结 - - - - - - -第 6 页,共 32 页精选学习资料 - - - - - - - - - HeapAdjustr.base,1,i-1 ； /将 r.base1.i-1 重新调整为大顶堆 void HeapAdjustchar *r,int k,int m i=k ； x=ri ； j=2*i ； / 沿 key 较大的孩子节点向下挑选 whilej /j 为 key 较大的记录的下标 if j & rjrj+1 j+ ；ifxrj / 插入字符比当前

14、的大,交换 ri =rj ；i = j ；j *= 2 ； else /否就比较停止；j = m + 1 ； ri = x ； / 把字符 x 插入到该位置,元素插入实现 3.6归并排序算法思想：先将相邻的个数为1 的每两组数据进行排序合并；然后对上次归并所得到的大小为2的组进行相邻归并；如此反复,直到最终并成一组,即排好序的一组数据；程序实现及核心代码的注释：void mergeSqList6 r,int h ,int m ,int w ,SqList6 t / 对相邻两组数据进行组合排序；int i,j,k ；i = h ；j = m + 1 ； /j 为合并的其次组元素的第一个数位置 k

15、 =h-1； / k 为存入 t 中的数的位置；whilei &j / 依次排列两组数据 k+； ifr.basei / 将第一组数据与其次组数据分别比较；7 / 32 名师归纳总结 - - - - - - -第 7 页,共 32 页精选学习资料 - - - - - - - - - t.basek = r.basei+ ；else t.basek = r.basej+ ； ifi m / 第一组数据先排完的情形 whilej t.base+k=r.basej+；else whilei t.base+k=r.basei+； void tgbint s,int n,SqList6 r,SqList

16、6 t / 对数据进行每组 s 个数的归并排序；int i=1 ； /i 为要合并两组元素的第一个数位置；whilei merger,i,i+s-1,i+2*s-1,t ； /i+s-1 为要合并的第一组元素的最终一 /数位置、 i+2*s-1 为要合并的两 组元素/最终一个数位置；i=i+2*s ； ifi / 考虑 n 不能被 s 整除,假如余下的数少于 /2*s 但大于 s,也就是余下的数 不能凑成/两组,凑一组有余 ,就把余下的 数进行组/合,并对其进行排序；merger,i,i+s-1,n,t ；else /假如余下的数少于s,就余下的数进行组/合,并进行排序；whilei t.ba

17、sei=r.basei+ ； void gbFILE *fp / 归并主函数； n = r.length；8 / 32 名师归纳总结 - - - - - - -第 8 页,共 32 页精选学习资料 - - - - - - - - - SqList6 t ；t.base=char * mallocr.stacksize*sizeofchar ； /给待排序的数组 t 申请内存； whiles / 每组元素不断增加循环进行合并排序； tgbs,n,r,t； / s 为每组元素的个数、n 为元素总个数、r / 为原数组, t 为待排序的数组,进行归并排 s*=2 ； / 序；把元素个数相同的两组合并

18、 并进行重新 / 定义成新的一组,此组元素个数为 2*s；ifs tgbs,n,t,r ； s *= 2； /当元素个数小于 n 时,对其进行合并排序； 3.7冒泡排序 算法思想：1、先将一组未排序的数组的最终一个数与倒数其次个数进行比较,并将较小的数放于两个数中较前的位置,然后将比较后的较小的数与倒数第三个进行比较,依次比较到第一个数,即可得到第一个数是全部数中最小的数；2、然后再将数组的最终一个数与倒数其次个数进行比较,并将较小的数放于两个数中较前的位置,依次比较到其次个数,3、如此循环到只剩最终两个比较,即得到排好序的一组数；程序实现及核心代码的注释：for i=0 ； i / i 为排

19、好序的数的下标,依次往后存放排好序的数； for j = r.length-2 ；j = i ；j - / 从后往前依次两两比较,较小的被调换到前面； ifr.basej+1 / 比较相邻两个数,假如后面的小于前面的,向下执行； 9 / 32 名师归纳总结 - - - - - - -第 9 页,共 32 页精选学习资料 - - - - - - - - - temp = r.basej+1 ； /将后面的较小的数储存起来；r.basej+1 = r.basej ； /将前面的较大的数放在后面较小的数的位置；r.basej = temp； / 将较小的数放在前面的较大的数的位置； 4.调试 检测主

20、函数是否能够稳固运行 如图 4-1：图 4-1 5.调试及检验5.1 直接插入排序 输入字符并储存 如图 5-1.1）：调用算法【 1】处理文件 如图 5-1.2）：处理结果 如图 5-1.3）：10 / 32 名师归纳总结 - - - - - - -第 10 页,共 32 页精选学习资料 - - - - - - - - - 图 5-1.1 图 5-1.2图 5-1.35.2折半插入排序 输入字符并储存 如图 5-2.1）：调用算法【 2】处理文件 如图 5-2.2）：处理结果 如图 5-2.3）：图 5-2.1 图 5-2.2 图 5-2.3 5.3 希尔排序 输入字符并储存 如图 5-3.

21、1）：调用算法【 3】处理文件 如图 5-3.2）：11 / 32 名师归纳总结 - - - - - - -第 11 页,共 32 页精选学习资料 - - - - - - - - - 处理结果 如图 5-3.3）：图 5-3.1 图 5-3.2图 5-3.3 5.4简洁挑选排序输入字符并储存 如图 5-4.1）：调用算法【 4】处理文件 如图 5-4.2）：处理结果 如图 5-4.3）：图 5-4.1 图图 5-4.3 5.5堆排序名师归纳总结 - - - - - - -第 12 页,共 32 页精选学习资料 - - - - - - - - - 输入字符并储存 如图 5-5.1）：调用算法【

22、5】处理文件 如图 5-5.2）：处理结果 如图 5-5.3）：图 5-5.1 图 5-5.2 图 5-5.3 5.6归并排序 输入字符并储存 如图 5-6.1）：调用算法【 6】处理文件 如图 5-6.2）：处理结果 如图 5-6.3）：13 / 32 名师归纳总结 - - - - - - -第 13 页,共 32 页精选学习资料 - - - - - - - - - 图 5-6.1 图 5-6.2图 5-6.3 5.7冒泡排序 输入字符并储存 如图 5-7.1）：调用算法【 7】处理文件 如图 5-7.2）：处理结果 如图 5-7.3）：图 5-7.1 图图 5-7.314 / 32 名师归

23、纳总结 - - - - - - -第 14 页,共 32 页精选学习资料 - - - - - - - - - 6.测试与比较6.1调试步骤 在 kcsj 文本文件中随机输入一串字符串,然后储存下来并且复制备份在桌面上；运行程序,调用 不算法去处理文件；用秒表运算从开头到终止所用的时间,并记录下来；将文件夹中的 kcsj 文本文件删除,将桌面上的备份文件考入文件夹来代替原文件,以保证被操作 数据的一样性；用同样的方法依次测试七种算法所用的时间,并记录下来；再将数据依次转变为占用内存大小为 以上的操作；将记录的数据 1m 1.5s 0.2s 6.0s 0.1s 3m 5.5s 1.1s 23s 0

24、.1s 0.1s 24s 200KB - 20s 3.8s - 0.1s 1m 512KB - 1m 14s - 3m 1024KB - 3m 1m - 0.2s 0.3s 10m -：表示时间过长 6.2结论 通过试验结果的比较与分析我们发觉：直接插入排序、冒泡排序、简洁挑选排序及折半插入排序是 低效率的排序方式；所以我们实际编程重要尽可能的防止他们的显现；我们应当用较先进的归并排 序及堆排序；7.试验心得与分析通过本次课程设计,我们小组的每个成员都学到了许多东西；第一要说的是我们的编程才能,在 这一次的课程设计中我们的编程才能均得到了肯定程度的提升；并且通过这次课程设计,我们更加 熟识了如

25、何使用 Header File 文件；本次课程设计,让我们对于直接插入排序,折半插入排序,希尔 排序,简洁挑选排序,堆排序,归并排序,冒泡排序等七种排序算法的思想有了进一步的熟识,同 时对七种算法的应用有了更进一步的把握；通过这次课程设计,我们对于解决实际问题的才能有了 进一步提高；最重要的是,这次课程设计大大的训练了我们的小组团队协作才能；通过这次课程设 计我们小组各成员的团队协作才能都有了很大的提升；这种团队协作才能对于我们学编程的来说是15 / 32 名师归纳总结 - - - - - - -第 15 页,共 32 页精选学习资料 - - - - - - - - - 极其重要的,同时也是必

26、不行少的；当然,我们写程序的时候遇到了许多困难；而且在程序调试过程中显现了许多错误与警告,不过 在队员及老师的帮忙下均得到明白决；当程序可以运行后,程序的运行过程中同样也也显现了许多 错误,甚至显现了不兼容的情形；不过,后来在队员及老师的帮忙下也均得到明白决；然而,我们的程序仍有一点瑕疵让我们感到美中不足；那就是在归并算法运行过程中,当输入为 9 个字符时,排序结果会显现偶然误差；经过分析,我们认为这点是系统的问题；不过,这仍旧是一点让我们感 到遗憾的地方；8.附录8.1直接插入排序 #include #include #define Q 1000 typedef struct char *b

27、ase ；int stacksize ；int length ；SqList1 ；void zjFILE *fp SqList1 r ；int i,j ；char temp,*p ； r.base=char * mallocQ*sizeofchar；r.stacksize = Q；r.length = 0； while.feoffp fscanffp,%c,r.base ；r.base+；r.length+ ；ifr.length = r.stacksize 16 / 32 名师归纳总结 - - - - - - -第 16 页,共 32 页精选学习资料 - - - - - - - - - r.

28、base= r.base - r.length；r.base=char * reallocr.base,r.stacksize + Q * sizeofchar ；if.r.base printfERROR ；return ； r.base = r.base + r.stacksize；r.stacksize += Q； r.length - ；r.base -；r.base= r.base - r.length；for i = 1 ； i forj=0 ；j ifr.basei temp = r.basei；fori= i ；i j ； -i r.basei = r.basei-1 ；r.b

29、asej = temp； r.baser.length =0 ；rewindfp ；fprintffp,%s,r.base ；fclosefp ；freer.base； 8.2折半插入排序 #include #include 17 / 32 名师归纳总结 - - - - - - -第 17 页,共 32 页精选学习资料 - - - - - - - - - #define Q 1000 typedef struct char *base ；int stacksize ；int length ；SqList2 ；void zbFILE *fp SqList2 r ；int i,j ,m, low,

30、 high ；char temp； r.base=char * malloc1000*sizeofchar；r.stacksize = 1000；r.length = 0； while.feoffp fscanffp,%c,r.base ；r.base+；r.length+ ；ifr.length = r.stacksize r.base= r.base - r.length；r.base=char * reallocr.base,r.stacksize + Q * sizeofchar ；if.r.base printfERROR ；return ； r.base = r.base + r.

31、stacksize；r.stacksize += Q； r.length - ；18 / 32 名师归纳总结 - - - - - - -第 18 页,共 32 页精选学习资料 - - - - - - - - - r.base -；r.base= r.base - r.length；for i = 1 ； i temp=r.basei ；low=0 ；high=i-1 ；while low m = low+high/2 ；if temp high = m-1 ；else low = m+1 ； for j=i-1 ； j=high+1 ； -j r.basej+1= r.basej ；r.bas

32、ehigh+1=temp ； r.baser.length =0 ；rewindfp ；fprintffp,%s,r.base ；fclosefp ；freer.base； 8.3希尔排序 #include #include #define Q 1000 typedef struct char *base ；int stacksize ；int length ；19 / 32 名师归纳总结 - - - - - - -第 19 页,共 32 页精选学习资料 - - - - - - - - - SqList3 ；void xeFILE *fp SqList3 r ；int i,j,k,m ；cha

33、r temp；r.length = 0； r.base=char * malloc1000*sizeofchar；r.stacksize = 1000； while.feoffp fscanffp,%c,r.base ；r.base+；r.length+ ；ifr.length = r.stacksize r.base= r.base - r.length；r.base=char * reallocr.base,r.stacksize + Q * sizeofchar ；if.r.base printfERROR ；return ； r.base = r.base + r.stacksize；

34、r.stacksize += Q； r.length - ；r.base -；r.base= r.base - r.length；fork = 0 ； k 20 / 32 名师归纳总结 - - - - - - -第 20 页,共 32 页精选学习资料 - - - - - - - - - m = 10 - k ；for i = m ； i ifr.basei temp = r.basei；forj = i - m ； j = 0 & temp r.base j + m = r.basej ；r.base j + m = temp ； rewindfp ；fprintffp,%s,r.base ；fclosefp ；freer.base； 8.4简洁挑选排序 #include #include #define