没有合适的资源?快使用搜索试试~ 我知道了~
基于插入排序方法的类模板设计与实现.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 144 浏览量
2023-06-25
22:53:32
上传
评论
收藏 375KB DOC 举报
温馨提示
试读
23页
基于插入排序方法的类模板设计与实现.doc
资源推荐
资源详情
资源评论
摘 要
排序是计算机程序设计中的一种重要运算,它的功能是将一个数据元素(或
记录)的任意序列重新排列成一个按关键字有序的序列。简言之,所谓排序就是
根据关键字值的非递减或非递增次序,把文件中的各记录依次排列起来,可使一
个无序文件变成有序文件的一种操作。有一个已经有序的数据序列,要求在这个
已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时
候就要用到一种新的排序方法——插入排序法。插入排序包括:直接插入排序,
折半插入排序,2-路插入排序,表插入排序,希尔排序。
关键词:直接插入排序法;2—路插入排序法;希尔排序法;MFC 工程
目 录
1 需求分析....................................................................................................................1
2 算法基本原理............................................................................................................2
3 类设计........................................................................................................................3
4 基于控制台的应用程序..........................................................................................4
4.1 类的接口设计 ....................................................................................................4
4.2 类的实现 ............................................................................................................5
4.3 主函数设计 ........................................................................................................7
4.4 基于控制台的应用程序测试 ............................................................................9
5 基于 MFC 的应用程序 .........................................................................................10
5.1 基于 MFC 的应用程序设计............................................................................10
5.1.1 MFC 程序界面设计 ..........................................................................10
5.1.2 MFC 程序代码设计 ..........................................................................13
5.2 基于 MFC 的应用程序测试..............................................................................17
结 论............................................................................................................................20
参考文献......................................................................................................................21
沈阳理工大学课程设计
0
1 需求分析
(1)有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,
但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序
法。插入排序包括:直接插入排序,折半插入排序,2-路插入排序,表插入排序,希尔
排序。
(2)插入排序的基本思想是:在一个已排好序的记录子集的基础上,每一步将下
一个待排序的记录有序地插入到已排好序的记录子集中,知道将所有待排记录全部插入
为止。这很像打扑克牌时,没抓一张牌,插入到合适位置,知道抓完牌为止,即可得到
一个有序序列。
(3) 直接插入排序:将一个记录插入到已排序好的有序表中,从而得到一个新的、
记录数增 1 的有序表。设整个排序有 n 个数,则进行 n-1 趟插入,即:先将序列中的第
1 个记录看成是一个有序的子序列,然后从第 2 个记录起逐个进行插入,直至整个序列
变成按关键字非递减有序列为止。
(4)2-路插入排序是在折半插入排序的基础上的发展。其目的是减少排序过程中
记录移动的次数,但为此需 n 个记录的辅助空间。具体做法是:另设一个和 L. r 同类型
的数组 d,首先将 L. r [1]赋值给 d[1],将 d[1]看成是排好序的序列中处于中间位置的记
录,然后从 L. r 中第 2 个记录起依次插入到 d[1]之前或之后的有序序列中。先将待排序
记录的关键字和 d[1]的关键字比较,若 L.r[i].key< d[1] .key ,则将 L.r[i]插入到 d[1]之
前的有序表中。反之,将 L.r[i]插入到 d[1]之后的有序表中。在实现算法时,将 d 看成
一个循环向量,并设两个指针 first 和 final 分别指示排序过程中得到的有序序列中的第
一个记录和最后一个记录在 d 中的位置。
(5)希尔排序又称“缩小增量排序”,它属于插入排序类。它的基本思想是:先将整个
待排序的记录分割成若干子序列分别进行“直接插入排序”,待整个序列中的记录”基本
有序“时,再对全体记录进行一次直接插入排序。
沈阳理工大学课程设计
1
2 算法基本原理
(1)直接插入排序算法:
排序过程为:将一个记录插入到已排序好的有序表中,从而得到一个新的、记录数
增 1 的有序表。设整个排序有 n 个数,则进行 n-1 趟插入,即:先将序列中的第 1 个记
录看成是一个有序的子序列,然后从第 2 个记录起逐个进行插入,直至整个序列变成按
关键字非递减有序列为止。直接插入排序过程如图 2.1 所示:
(2)2-路插入排序算法:
排序过程为:另设一个和 L. r 同类型的数组 d,首先将 L. r [1]赋值给 d[1],将 d[1]
看成是排好序的序列中处于中间位置的记录,然后从 L. r 中第 2 个记录起依次插入到
d[1]之前或之后的有序序列中。先将待排序记录的关键字和 d[1]的关键字比较,若
L.r[i].key< d[1] .key ,则将 L.r[i]插入到 d[1]之前的有序表中。反之,将 L.r[i]插入到 d[1]
之后的有序表中。在实现算法时,将 d 看成一个循环向量,并设两个指针 first 和 final
分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在 d 中的位置。
2-路插入排序过程如图 2.2 所示:
(3)希尔排序算法:
(3)希尔排序算法:
初始关键字 ( 49 ) 38 65 97 76 13 27 49
i=2: ( 38 49 ) 65 97 76 13 27 49
i=3: ( 38 49 65 ) 97 76 13 27 49
i=4: ( 38 49 65 97 ) 76 13 27 49
i=5: ( 38 49 65 76 97 ) 13 27 49
i=6: ( 13 38 49 65 76 97 ) 27 49
i=7: ( 13 27 38 49 65 76 97 ) 49
i=8: ( 13 27 8 49 49 65 76 97 )
图 2.1 直接插入排序过程图
初始关键字 45 62 35 77 92 55 14 35
排序过程中 d 的状态如下:
初始状态 (45) final=1 first=9
i =2 (45 62) final=2 first=9
i =3 (45 62) (35) final=2 first=8
i =4 (45 62 77) (35) final=3 first=8
i =5 (45 62 77 92) (35) final=4 first=8
i =6 (45 55 62 77 92) (35) final=5 first=8
i =7 (45 55 62 77 92) (14 35) final=5 first=7
i =8 (45 55 62 77 92) (14 35 35) final=5 first=6
图 2.2 2-路插入排序过程图
沈阳理工大学课程设计
2
(3)希尔排序算法:
基本思想是:先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”,
待整个序列中的记录”基本有序“时,再对全体记录进行一次直接插入排序。希尔排序
过程如下图 2.3:
初始关键字: 49 38 65 97 76 13 27 49 55 04
13 27 49 55 04 49 38 65 97 76
图 2.3 希尔排序过程图
3 类设计
从上面的过程分析可以看到,本设计的关键所在是对所输入数据分别进行三种不同
的排序,所输入的数据有两种类型,分别为 int 型和 char 型。对于两种不同的数据类型,
可以先建立一个类模板,虚拟类型名为 Type 型,类模板名为 Sort。在主函数 main()
中建立两个对象,分别制定对象类型为 int 型和 char 型。
在虚拟类中声明各成员函数:void write()读入数组函数;void InsertionSort()
直接插入排序函数;void Srsort(Type mi[])二路排序;void ShellSort(Type da[],int k)
void Shellinsert(Type dk)希尔排序。Void print()输出排序结果函数。分别在类模板
外声明各成员函数。
4 基于控制台的应用程序
整个程序三部分。首先是声明类模板,其中包括输入输出数据成员函数的声明以及
直接插入排序,2—路排序,希尔排序的成员函数声明。其次是在类外对所有成员函数
进行定义。最后在主函数中实现数据的排序操作。
一趟排序结果:
二趟排序结果:
13 04 49 38 27 49 55 65 97 76
三趟排序结果:
04 13 27 38 49 49 55 65 76 97
剩余22页未读,继续阅读
资源评论
老帽爬新坡
- 粉丝: 82
- 资源: 2万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功