一、题目：排序算法应用二（直接法、插入法、shell排序）
二、目的与要求
1． 目的：
通过排序算法的设计，培养学生综合利用C++语言进行程序设计的能力，加强函数的运用及学生对软件工程方法的初步认识，提高软件系统分析能力和程序文档建立、归纳总结的能力，掌握排序算法，使学生能够解决信息管理系统中的一些问题。
2． 基本要求：
（1）要求用C++语言编程，在Visual C++环境下调试完成；
（2）要求各个功能分别使用函数来完成；
（3）分析算法的时间复杂度和空间复杂度。
三、设计方法和基本原理
1． 课题功能描述
课题实现的功能是将一组无序数列通过排序使其成为有序数列。
2． 问题详细描述
将一组无序数列分别通过直接法、插入法、shell排序进行排序，使其按一定规律（由大到小或由小到大）排列。
3．问题的解决方案：
根据问题的描述，可以按照要求的功能采用结构化的设计思想。
（1） 数列的赋值要求用函数实现。
（2） 使用“直接法”进行排序，用函数实现并统计排序次数。
（3） 使用“插入法”进行排序，用函数实现并统计排序次数。
（4） 使用“希尔法”进行排序，用函数实现并统计排序次数。
（5） 比较以上排序方法的优劣。
四、主要技术问题的描述
根据三的分析，主要解决的问题在于：
1、“直接法”排序的实现（由大到小排序）。
算法描述如下：
直接法排序（也称比较互换法）是比较直观易于理解的一种排序方法。方法是：将数组A 中的第一个元素与其后面的每一个元素逐个比较，凡是比第一个元素大的数就立即和第一个元素交换，待一轮比较互换完毕，则第一个元素即为数组A中最大的元素；然后将数组A 中的第二个元素与其后的每个元素比较，并进行必要的互换，待第二轮比较完毕，第二个元素即为第二大元素。照此下去，进行N-1轮“比较互换”后，即将N个元素排好。
上述直接排序过程，可用两层循环来实现，外循环控制“轮数”，内层循环用于完成每轮中的“比较互换”。
2、“插入法”排序的实现（由大到小排序）。
基本思想：将一张表分成已排好序的表和未排序的表两部分，每次从未排序的表中提取一个元素插入到已排序的表中的恰当位置。刚开始时，已排好序的表只有一个元素，按上述的做法操作到未排好序的表为空后，即可得到一张排好序的表。例如：
排序前： 13，15，39，22，44，27，43
第一次扫描： 15，13，39，22，44，27，43
第二次扫描： 39，15，13，22，44，27，43
第三次扫描： 39，22，15，13，44，27，43
第四次扫描： 44，39，22，15，13，27，43
第五次扫描： 44，39，22，27，15，13，43
第六次扫描： 44，43，39，22，27，15，13
排序完毕：44，43，39，22，27，15，13
分析：在未扫描前，取第一个元素13作为已排好序的表。第一次扫描该线性表时，取未排好序的表中的第一个元素15插入到13前，第二次扫描时，从剩余的表中取出39插入大15和13前，依次类推，由于表中共7个元素，因此总共进行7-1=6次插入操作，就完成了对该表的排序。
3、shell法排序
shell排序算法的实现方法如下：
第一步：任意选定进行比较的两个元素的距离H，把A（I）与A（I+H）比较，若A（I）大于A（I+H）则把这两个元素中的数据进行对调，把小的放在前面，大的放在后面，即“比较对调”。如果是N个元素，则I从1变化到N-H，对于每一个I值进行一次“比较对调”操作。I从1变到N-H进行的全部“比较对调”为“一趟”。在一趟的扫描中，只要有对调，则H保持不变，重复进行一趟操作，直到没有对调。
第二步：改变H的值（新的H小于老的H值），用新H重复上述过程，直到H=1且以此为距离进行一趟的操作中没对调发生为止，排序完成。
例如：将数列（数组）A为2 6 1 8 4 7 3由小到大排序。具体描述如下：
2 6 1 8 4 7 3 H=5，在一趟中A[0]和A[5]比较未对调， A[1]和A[6]进行对调
2 3 1 8 4 7 6 H=5（H不变），进行一趟比较中没有发生对调
2 3 1 8 4 7 6 H=3，在一趟中A[0]与A[3]，A[1]与A[4]，A[2]与A[5]，都没对调
A[3]与A[6]进行对调
2 3 1 6 4 7 8 H=3（H不变），进行一趟比较中没有发生对调
2 3 1 6 4 7 8 H=2，在一趟比较中A[0]与A[2]发生对调
1 3 2 6 4 7 8 H=2（H不变），进行一趟比较中没有发生对调
1 3 2 6 4 7 8 H=1，在一趟比较中A[1]与A[2]， A[3]与A[4]发生对调
1 2 3 4 6 7 8 H=1（H不变），进行一趟比较中没有发生对调，直至排序完成
五、创新要求
在基本要求达到后，进行创新设计:
（1）使用多文件，即主函数和各个函数分别存放在不同的.cpp文件中，在头文件中进行函数原型声明；
（2）采用复杂数据结构实现排序算法，如结构。
