基于插入排序方法的类模板设计与实现

《基于插入排序方法的类模板设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、成绩评定表学生姓名郝晓鹏班级学号1103060129专业通信工程课程设计题目基于插入排序方法的类模板设计与实现评语组长签字：成绩日期20年月日课程设计任务书学院信息科学与工程专业通信工程学生姓名郝晓鹏班级学号1103060129课程设计题目基于插入排序方法的类模板设计与实现实践教学要求与任务建立一维数组数据结构的模板类，使一维数组中的数据元素可以是char,int,float等多种数据类型，并对数组元素实现插入类排序。主要完成如下功能：（1）实现数组数据的输入和输出；（2）实现直接插入排序功能；（3）实现2-路插入排序功能；（4）实现希尔排序功能；（5）将每种排序功能作为类的成员函数实现，编

2、写主函数测试上述排序功能。工作计划与进度安排第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师：201年月日专业负责人：201年月日学院教学副院长：201年月日摘要排序是计算机程序设计中的一种重要运算，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。简言之，所谓排序就是根据关键字值的非递减或非递增次序，把文件中的各记录依次排列起来，可使一个无序文件变成有序文件的一种操作。有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数

3、据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。插入排序包括：直接插入排序，折半插入排序，2-路插入排序，表插入排序，希尔排序。关键词：直接插入排序法；2—路插入排序法；希尔排序法；MFC工程目录1需求分析12算法基本原理23类设计34基于控制台的应用程序44.1类的接口设计44.2类的实现54.3主函数设计74.4基于控制台的应用程序测试95基于MFC的应用程序105.1基于MFC的应用程序设计105.1.1MFC程序界面设计105.1.2MFC程序代码设计135.2基于MFC的应用程序测试17结论20参考文献21沈阳理工大学课程设计1需求分析（1）有一个已经有序的数据序列

4、，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。插入排序包括：直接插入排序，折半插入排序，2-路插入排序，表插入排序，希尔排序。（2）插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，知道将所有待排记录全部插入为止。这很像打扑克牌时，没抓一张牌，插入到合适位置，知道抓完牌为止，即可得到一个有序序列。（3）直接插入排序：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。设整个排序有n个数，则进行n-1趟插入，即：先将序列中的第1个

5、记录看成是一个有序的子序列，然后从第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

6、。在实现算法时，将d看成一个循环向量，并设两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。(5)希尔排序又称“缩小增量排序”，它属于插入排序类。它的基本思想是：先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”，待整个序列中的记录”基本有序“时，再对全体记录进行一次直接插入排序。20沈阳理工大学课程设计2算法基本原理（1）直接插入排序算法：排序过程为：将一个记录插入到已排序好的有序表中，从而得到一个新的、记录数增1的有序表。设整个排序有n个数，则进行n-1趟插入，即：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记

7、录起逐个进行插入，直至整个序列变成按关键字非递减有序列为止。直接插入排序过程如图2.1所示：初始关键字(49)38659776132749 i=2:(3849)659776132749 i=3:(384965)9776132749 i=4:(38496597)76132749 i=5:(3849657697)132749 i=6:(133849657697)2749 i=7:(13273849657697)4