题目3. 排序算法功能的演示
一、需求分析。
1.运行环境（软、硬件环境）
microsoft visual studio 2010专业版（windows7）
2.程序所实现的功能；
1. 待演示的排序算法如下：
1） 直接插入排序；
2） 冒泡排序；
3） 简单选择排序；
4） 快速排序；
5） 堆排序；
6） 归并排序。
2. 显示。
1）显示所演示的排序算法的名称。
2）给出提示输入一组关键字，建立排序表。
3）显示初始的排序表的各个关键字。
4）显示每一趟的趟数以及每一趟的结果。
3程序的输入：包含输入的数据格式和说明。
（1)排序种类三输入。
(2)排序数的个数的输入。
3)所需排序的所有数的输入。
4程序的输出：程序输出的形式。
(1)主菜单的输出。
2)每一趟排序的输出，即排序过程的输出。
5测试数据，如果程序输入的数据量比较大，需要给出测试数据。
测试数据为根据需求随机输入的整数。
二、设计说明。
1. 算法设计的思想。
1）交换排序（冒泡排序、快速排序）
交换排序的基本思想是：对排序表中的数据元素按关键字进行两两比较，如果发生逆序（即排列顺序与排序后的次序正好相反），则两者交换位置，直到所有数据元素都排好序为止。
2）插入排序（直接插入排序）
插入排序的基本思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。
然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。
3）选择排序（简单选择排序、堆排序）
选择排序的基本思想是：第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。
（4）归并排序（两路归并排序）
两路归并排序的基本思想是：假设初始排序表有n个数据元素，首先把它看成是长度为1的首尾相接的n个有序子表（以后称它们为归并项），先做两两归并，得n/2上取整个长度为2的归并项（如果n为奇数，则最后一个归并项的长度为1）；再做两两归并，……如此重复，最后得到一个长度为n的有序序列。
2.主要的数据结构设计说明。
const int maxsize=100;//最多可输入100个数。
int num=0;//定义全局变量，为每一趟的输出做准备。
int x=0;
templateclass sortlist//定义排序类。
private:
int currentsize;//数据表中数据元素的个数。
public:
type *arr;//存储数据元素的向量（排序表）
sortlist():currentsize(0)//构造函数。
sortlist(int n)
void insert(int i,type x)
~sortlist()/析构函数。
void swap(type &x,type &y)//数据元素x和y交换位置。
void insertionsort();直接插入排序。
void bubblesort();冒泡排序。
void selectsort();简单选择排序。
void quicksort(int low,int high);/快速排序。
void heapsort();堆排序。
void mergesort(sortlist &table);/归并排序。
void filterdown(const int start);/建立最大堆。
void mergepass(sortlist&sourcetable,sortlist&mergedtable,co nst int len);/一趟归并。
void merge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right);/两路归并算法。
3.程序的主要流程图。
4.程序的主要模块，要求对主要流程图**现的模块进行说明。
(1)主菜单。
主要功能：程序运行时，可使运行者根据提醒输入相关操作，从而进入不同的排序方法或者退出。
(2)排序方法及输出。
根据运行者对排序的不同选择，进入排序过程。
1.直接插入排序：根据直接排序的算法，输出排序过程。
2.冒泡排序：根据冒泡排序算法，输出排序过程。
3.简单选择排序：根据简单选择排序的算法，输出排序过程。
4.快速排序：根据快速排序的算法，输出排序过程。
5.堆排序：根据堆排序的算法，输出排序过程。
6.归并排序：根据归并排序的算法，输出排序过程。
5程序的主要函数及其伪**说明 (不需要完整的**)
1）模板类。
主要说明程序中用到的类的定义。
templateclass sortlist
private:
int currentsize;//数据表中数据元素的个数。
public:
type *arr;//存储数据元素的向量（排序表）
sortlist():currentsize(0)//构造函数。
sortlist(int n)
void insert(int i,type x)
~sortlist()/析构函数。
void swap(type &x,type &y)//数据元素x和y交换位置。
void bubblesort();冒泡排序。
void quicksort(int low,int high);/快速排序。
void insertionsort();直接插入排序。
void selectsort();简单选择排序。
void heapsort();堆排序。
void mergesort(sortlist &table);/归并排序。
void filterdown(const int start);/建立最大堆。
void mergepass(sortlist&sourcetable,sortlist&mergedtable,const int len);/一趟归并。
void merge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right);/两路归并算法。
（2）直接插入排序。
直接插入排序的基本思想：开始时把第一个数据元素作为初始的有序序列，然后从第二个数据元素开始依次把数据元素按关键字大小插入到已排序的部分排序表的适当位置。当插入第i(1以下是在顺序表上实现的直接插入排序。
在顺序表上进行直接插入排序时，当插入第i(1伪**如下。
template //直接插入排序。
void sortlist::insertionsort()
type temp;
int j;
for(int i=1;i<=currentsize-1;i++)
arr[j+1]=temp;
cout<<"第"< for(int t=0;t cout< cout< } num=0; 3）冒泡排序。 冒泡排序的基本思想是：设排序表中有n个数据元素。首先对排序表中第一，二个数据元素的关键字arr[0]和arr[1]进行比较。 如果前者大于后者，则进行交换；然后对第二，三个数据做同样的处理；重复此过程直到处理完最后两个相邻的数据元素。我们称之为一趟冒泡，它将关键字最大的元素移到排序表的最后一个位置，其他数据元素一般也都向排序的最终位置移动。然后进行第二趟排序，对排序表中前n-1个元素进行与上述同样的操作，其结果使整个排序表中关键字次大的数据元素被移到arr[n-2]的位置。 如此最多做n-1趟冒泡就能把所有数据元素排好序。 东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问... 设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供... 河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...数据结构课程设计报告
数据结构课程设计报告
数据结构课程设计报告