1、 1 数据结构课程设计报告数据结构课程设计报告 几种排序算法的演示几种排序算法的演示 班级：班级： 姓名：姓名： 学号：学号： 完成日期：完成日期： 一一 需求分析需求分析 1.运行环境 Microsoft Visual Studio 2008 2.程序所实现的功能 对直接插入排序、折半插入排序、冒泡排序、简单选择排序、快速排序、堆排序、归并 排序算法的演示，并且输出每一趟的排序情况。 3.程序的输入（包含输入的数据格式和说明） 排序种类三输入 排序数的个数的输入 所需排序的所有数的输入 4.程序的输出（程序输出的形式） 主菜单的输出 每一趟排序的输出，即排序过程的输出 5.测试数据，如果程序
2、输入的数据量比较大，需要给出测试数据。 二 设计说明 1.算法设计思想算法设计思想 交换排序（冒泡排序、快速排序） 交换排序的基本思想是： 对排序表中的数据元素按关键字进行两两比较， 如果发生逆序 （即排列顺序与排序后的次序正好相反） ，则两者交换位置，直到所有数据元素都排好序为 止。 插入排序（直接插入排序、折半插入排序） 插入排序的基本思想是： 每一次设法把一个数据元素插入到已经排序的部分序列的合适 位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数 据元素。然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序 列后，整个排序工作就完成了。
3、 选择排序（简单选择排序、堆排序） 选择排序的基本思想是： 第一趟在有 n 个数据元素的排序表中选出关键字最小的数据元 素，然后在剩下的 n-1 个数据元素中再选出关键字最小（整个数据表中次小）的数据元素， 依次重复，每一趟（例如第 i 趟，i=1，n-1）总是在当前剩下的 n-i+1 个待排序数据元 素中选出关键字最小的数据元素，作为有序数据元素序列的第 i 个数据元素。等到第 n-1 趟 选择结束， 待排序数据元素仅剩下一个时就不用再选了， 按选出的先后次序所得到的数据元 素序列即为有序序列，排序即告完成。 归并排序（两路归并排序） 两路归并排序的基本思想是： 假设初始排序表有 n 个数据
4、元素， 首先把它看成是长度为 1 的首尾相接的 n 个有序子表 （以后称它们为归并项） ，先做两两归并，得 n/2 上取整个长度 为 2 的归并项（如果 n 为奇数，则最后一个归并项的长度为 1） ；再做两两归并，如 此重复，最后得到一个长度为 n 的有序序列。 2 2.程序的主要流程图程序的主要流程图 3.程序的主要模块程序的主要模块(要求对主要流程图中出现的模块进行说明要求对主要流程图中出现的模块进行说明) 程序的主要模块主要分为主菜单模块和排序算法演示模块。 主菜单 主要功能：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者 退出。 排序方法及输出 根据运行者对排序
5、的不同选择，进入排序过程 a.直接插入排序：根据直接排序的算法，输出排序过程 b.折半插入排序：根据折半插入的算法，输出排序过程 c.冒泡排序：根据冒泡排序算法，输出排序过程 d.简单选择排序：根据简单选择排序的算法，输出排序过程 开始 进入主菜单 选择排序方法 输出排序结果 直插 折半 冒泡 选择 快排 堆排 归并 退出系统 3 e.快速排序：根据快速排序的算法，输出排序过程 f.堆排序：根据堆排序的算法，输出排序过程 g.归并排序：根据归并排序的算法，输出排序过程 4. 程序的主要函数及其伪代码说明程序的主要函数及其伪代码说明 模板类模板类 主要说明程序中用到的类的定义 templatec
6、lass sortlist private: int currentsize;/数据表中数据元素的个数 public: type *arr;/存储数据元素的向量（排序表） sortlist():currentsize(0)arr=new typemaxsize;/构造函数 sortlist(int n)arr=new typemaxsize;currentsize=n; void insert(int i,type x)arri=x; sortlist()delete arr;/析构函数 void swap(type x=y;y=temp; void bubblesort();/冒泡排序 void quicksort(int low,int high);/快速排序 void insertionsort();/直接插入排序 void binaryinsertsort();/折半插入排序 void selectsort();/简单选择排序 void heapsort();/堆排序 void merges
