《数据结构》课程设计报告
实验五 排序
一、需求分析：
本演示程序用C++6.0编写，完成各种排序的实现，对输入的一组数字实现不同的排序方法，对其由小到大顺序输出。
（1）分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法进行编写。
（2）、对存储的函数即输入的数字进行遍历。 （3）、初始化函数对输入的数字进行保存。
（4）、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。这当中还包括了各个函数的调用的实现。
（5）、程序所能达到的功能：完成对输入的数字的生成，并通过对各排序的选择实现
1
数字从小到大的输出。
二、程序主要功能以及基本要求：
（1）、设计一个菜单，格式如下： 1、直接插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、选择排序 6、堆排序 7、退出
（2）、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。
三、系统框架图：
本程序包含了9个函数，它们分别是： （1）、直接插入排序的算法函数InsertSort（）。 （2）、希尔排序的算法函数ShellSort（）。 （3）、冒泡排序算法函数BubbleSort（）。 （4）、快速排序的算法函数Partition（）。 （5）、选择排序算法函数SelectSort（）。 （6）、堆排序算法函数HeapAdjust（）。 （7）、对存储数字的遍历函数Visit（）。 （8）、初始化函数InitSqList（）。 （9）、主函数main（）。
主函数 各个排序算法函数 对入数进遍初化 输的组行历始操作界面的设计，函数的调用。 四、详细设计
实现各个算法的主要内容，下面是各个函数的主要信息： （1）各个排序函数的算法：
2
一、直接插入排序 void InsertSort(SqList &L) { int i,j;
for( i=2; i<=L.length;i++) { if(L.r[i].key < L.r[i-1].key) { L.r[0] = L.r[i]; L.r[i] = L.r[i-1];
for( j=i-2; (L.r[0].key < L.r[j].key); j--)
L.r[j+1] = L.r[j];
L.r[j+1] = L.r[0];
}
}
}
二、希尔排序
void ShellSort(SqList &L) {
int i, j; int dk = 1;//增量 while(dk <=L.length/3)
dk = 3*dk+1;//增大增量
while(dk>0) { dk /= 3;//减小增量
for (i = dk; i <=L.length; i++) { L.r[0].key = L.r[i].key;
j = i;
3