数据结构课设内部排序算法研究的报告及源代码
5星 · 超过95%的资源 需积分: 44 112 浏览量
2009-09-05
12:03:08
上传
评论 8
收藏 226KB DOC 举报 
一．题目：内部排序算法研究
（1）设 n 个关键字均为整数(1≤n≤100000)
（2）设计 K 个内部排序算法(K≥5), 每个算法记录执行所需
的时间
（3）自动生成多组数据,每组数据含 n 个整数
(正序、逆序、随机分布)
（4）执行每个排序算法
（5）用图、表格数据分析说明在什么情况下
采用什么算法较好;
二．设计思想
本程序共有五个排序算法。分别是：冒泡排序，简单选择排序，快速排序，直
接插入排序，堆排序。
1．冒泡排序
从数组的第一个元素（a[0]）开始,将两两相邻元素进行比较，每次比较时
如果前一个元素大于后一个元素，则交换这两个元素的值。比较 n-1 后，n
个数最大的一个数被移到最后一个元素（下标为 n-1 的元素）的位置上，。
下轮比较仍然从第 0 个元素开始，对余下的 n-1 个数重复上述过程 n-2 次；
此轮结束后，n 个数中次大的一个被移到倒数第二的位置。如此过程重复
n-1 遍，当第 n-1 轮比较完之后，n 个数全部排序完毕。
2．简单选择排序
已知一组无序数据 a[1]、a[2]、……a[n]，需将其按升序排列。首先比较 a[1]与 a[2]的值，
若 a[1]大于 a[2]则交换两者的值，否则不变。再比较 a[1]与 a[3]的值，若 a[1]大于
a[3]则交换两者的值，否则不变。再比较 a[1]与 a[4]，以此类推，最后比较 a[1]与
a[n]的值。这样处理一轮后， a[1] 的 值 一 定 是这组数据中最小的。再将 a[2] 与
a[3]~a[n]以相同方法比较一轮，则 a[2]的值一定是 a[2]~a[n]中最小的。再将 a[3]与
a[4]~a[n]以相同方法比较一轮，以此类推。共处理 n-1 轮后 a[1]、a[2]、……a[n]就
以升序排列了。
3．快速排序
基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所
剩余16页未读，继续阅读
评论3
最新资源