C 课程设计任务书沈理工

成绩评定表。

课程设计任务书。

摘要。排序是计算机程序设计中的一种重要运算，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。简言之，所谓排序就是根据关键字值的非递减或非递增次序，把文件中的各记录依次排列起来，可使一个无序文件变成有序文件的一种操作。

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法。插入排序包括：直接插入排序，折半插入排序，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的应用程序 12

5.1 基于mfc的应用程序设计 12

5.1.1 mfc程序界面设计 10

5.1.2 mfc程序**设计 13

5.2基于mfc的应用程序测试 17

结论 21参考文献 22

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]的关键字比较，若 < d[1] .key ，则将插入到 d[1]之前的有序表中。

反之，将插入到 d[1]之后的有序表中。在实现算法时，将d 看成一个循环向量，并设两个指针first 和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。

5)希尔排序又称“缩小增量排序”，它属于插入排序类。它的基本思想是：先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”，待整个序列中的记录”基本有序“时，再对全体记录进行一次直接插入排序。

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]的关键字比较，若 < d[1] .

key ，则将插入到 d[1]之前的有序表中。反之，将插入到 d[1]之后的有序表中。在实现算法时，将d 看成一个循环向量，并设两个指针first 和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。

2-路插入排序过程如图2.2所示：

3）希尔排序算法：

（3）希尔排序算法：

3）希尔排序算法：

基本思想是：先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”，待整个序列中的记录”基本有序“时，再对全体记录进行一次直接插入排序。希尔排序过程如下图2.3：

初始关键字49 38 65 97 76 13 27 49 55 04

图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（）输出排序结果函数。

分别在类模板外声明各成员函数。

整个程序三部分。首先是声明类模板，其中包括输入输出数据成员函数的声明以及直接插入排序，2—路排序，希尔排序的成员函数声明。其次是在类外对所有成员函数进行定义。

最后在主函数中实现数据的排序操作。

#include<>

#define num 50

template声明一个模板，虚拟类型名为type

class sort类模板名为sort

private: int len;

public:

void write声明读入数组函数。

void insertionsort声明直接插入排序函数。

void srsort(type mi声明2-路插入排序函数。

void shellsort(type da,int t);

void shellinsert(type dk声明希尔排序函数。

void print声明输出结果函数。

type array[num];

C 课程设计任务书沈理工

C课程设计任务书

C 课程设计任务书

c 课程设计任务书

其他用户还读了