长沙学院课程设计说明书
题目内部排序算法的比较系(部) 计算机科学与技术系专业(班级) 软件八班
姓名张宁宁
学号2011022819
指导教师曾俊勇
起止日期
课程设计任务书
课程名称：数据结构与算法
设计题目：内部排序算法的比较已知技术参数和设计要求：
问题描述：
通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。
基本要求：
1待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于5种。
2 待排序的元素的关键字为整数。
3 比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。
4演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。
5 最后要对结果作简单的分析。
测试数据：
用伪随机数产生程序产生。
选作内容：
对不同的表长做试验分析两个指标相对于表长变化关系。
设计工作量：
40课时
工作计划：
班级时间节次教室内容指导教师
11软件8班15周周一1-4节致远楼1413 布置任务
曾俊勇15周周一5-8节致远楼1502 上机调试
15周周二1-4节I涵虚楼C3201 答疑
15周周二5-8节致远楼1503 上机调试
15周周三1-4节涵虚楼C3202 答疑
16周周一1-4节致远楼1413 上机调试
16周周一5-8节致远楼1502 上机调试
16周周二1-4节涵虚楼C3201 答疑
16周周二5-8节致远楼1503 上机调试
16周周三1-4节致远楼1408 答辩
指导教师签名：日期:
教研室主任签名：日期：
系主任签名：日期：
长沙学院课程设计鉴定表
姓名张宁宁学号2011022819 专业软件工程班级八班设计题目内部排序算法的比较指导教师曾俊勇指导教师意见：
评定等级：教师签名：日期：
答辩小组意见：
评定等级：答辩小组长签名：日期：
教研室意见：
教研室主任签名：日期：
系（部）意见：
系主任签名：日期：
说明课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类；
目录
摘要 (4)
第一章系统总体设计 (5)
2.1 原始数据 (5)
2.2 输出数据 (5)
2.3 系统架构设计 (5)
2.3.1 程序的主要模块 (5)
2.3.2进入排序过程 (5)
2.3.3程序流程 (6)
第二章算法与数据设计 (7)
3.1选择排序 (7)
3.2插入排序 (7)
3.3冒泡排序 (7)
3.4快速排序 (7)
3.5希尔排序 (8)
第三章总结 (9)
参考文献 (10)
附录代码A (11)
摘要
本次课程设计是在《数据结构》基础上设计的，它的目的是帮助同学更深入的了解《数据结构》这门课程，使同学达到熟练掌握的程度。课程设计其中一个内容是内部排序算法的比较，它要求通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。并且待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于5种；比较的指标为有关键字参加的比较次数和关键字的移动次数演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。用到的序的种类有：直接选择排序，冒泡排序，折半插入排序、快速排序、归并排序。通过这几种方法的比较：快速排序、归并排序的效率较高，但适合用于数据多的情况；插入排序的时间复杂度同于直接选择排序、冒泡排序，但它大大降低比较次数，所有它的效率高于直接选择排序，冒泡排序。
关键字：选择排序；冒泡排序；插入排序；快速排序；希尔排序
第一章系统总体设计
2.1 原始数据
用户输入关键字的个数，数据由随机序列生成器和特殊序列生成器生成。
2.2 输出数据
产生的序列分别用选择排序、插入排序、冒泡排序、快速排序、希尔排序等这些排序方法进行排序，输出关键字的排序时间、比较次数、移动次数。
2.3 系统架构设计
2.3.1 程序的主要模块
程序的主要模块主要模块排序算法演示模块
2.3.2进入排序过程
a.选择排序，根据简单选择排序的算法，输出排序时间、比较次数、移动次数
b.插入排序，根据插入排序算法，输出排序时间、比较次数、移动次数
c.冒泡排序，根据冒泡排序的算法，输出排序时间、比较次数、移动次数
d.快速排序，根据快速排序的算法，输出排序时间、比较次数、移动次数
e.希尔排序，根据归并排序的算法，输出排序时间、比较次数、移动次数
2.3.3程序流程
开始 随机获取20000个数据
选择排序
冒泡排序
插入排序
快速排序
希尔排序
这五种排序方法各自比较次数，移动次数，运行时间
步骤循环5
次
结束
第二章算法与数据设计
3.1选择排序
简单选择排序的每一趟都是从待排的数据元素中选出一个最小（最大）的一个元素，顺序的放在已经排好的数列的最后，直到全部待排序的数据元素排序完毕。
3.2插入排序
这是一种最简单的排序方法，它的基本操作时将一个记录插入到一个已经排好序的有序表中，从而得到一个新的记录数增1的有序表。其效率：从空间的角度来看待，它只需要一个辅助的空间，从时间上来看的话，排序的基本操作是比较两个关键字的大小和移动（本程序中将移动和交换看成一样）记录。在整个排序的过程中，当待排序列中的关键字非递减有序的话，那么比较次数最小n-1，且不需要移动，当待排序列逆序时，比较次数达到最大（n+2）（n-1）/2，记录的移动的次数也达到最大值（n+4）（n-1）/2。取平均值得时候直接插入排序的时间复杂度O(n²)。排序是稳定的。
3.3冒泡排序
这种排序的比较基本思想就是两两比较待排序的数据元素的大小，发现两个数据元素的次序相反时候，就进行交换，知道没有反序的数据为止。冒泡排序是一次的比较找出最小（最大）值，然后将其放置序列的最后一个位置，再将剩下的从第一个位置开始至n-i的位置进行重复的操作。
3.4快速排序
首先在r[1..n]中，第一趟，确定一个轴r[1]，并把轴上的关键字复制给r[0]。先从最高位开始比较,若r[1]>=r[high]，则high——；若r[1]r[1],r[high]=r[low],在低位找到第一个比r[1]大的数，依次重复上叙两个比较动作，直到全部比较完成，将r[i]放到"中间"某个位置上使得r[1]左边所有的关键字小于r[1]右边所有记的关键字，并保留该位置，使得数组分成了两组。再采用递归，直至每组只有一个数据，即已排好了序。
算法分析
就平均速度而言，快速排序是已知内部排序方法中最好的一种排序方法，其时间复杂度为
O(nlog(n))。但是，在最坏情况下（基本有序时）快速排序所需的比较次数和冒泡排序的比较次相同，其时间复杂度为O（n^2）。快速排序需要一个栈作辅助空间，用来实现递归处理左、右子两组。在最坏情况下，递归深度为n，因此所需栈的空间大小为O(n)数量级。快速排序是不稳定的。
