各种排序算法课程设计报告

1、封面本科学生课程设计任务书课程设计题目内部排序算法比较学院软件学院专业软件工程年级2008级已知参数和设计要求：问题描述各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。学生应完成的工作：基本要求（1）对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。（2）待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和

2、关键字移动次数（关键字交换计为3次移动）。测试数据由随机产生器决定。目前资料收集情况（含指定参考资料）：c+数据结构与程序设计 robert l.kruse alexander j.ryba 北京，清华大学出版社，2004.1课程设计的工作计划： 先制作规划大纲，在从基础的表开始做，再研究核心的算法，各种排序函数的实现，最后用其他辅助类用于实现效率的比较，和测试数据的产生。最后在优化程序，添加注释。任务下达日期 2010年 4 月 26 日完成日期 2010 年 5 月 30 日指导教师 （签名）学 生 （签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003重庆大学本

3、科学生课程设计任务书课程设计题目学院专业年级已知参数和设计要求：学生应完成的工作：目前资料收集情况（含指定参考资料）：课程设计的工作计划：任务下达日期 年 月 日完成日期 年 月 日指导教师 （签名）学 生 （签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。重庆大学本科学生课程设计任务书课程设计题目学院专业年级已知参数和设计要求：学生应完成的工作：目前资料收集情况（含指定参考资料）：课程设计的工作计划：任务下达日期 年 月 日完成日期 年 月 日指导教师 （签名）学 生 （签名）说明：1

4、、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。重庆大学本科学生课程设计任务书课程设计题目学院专业年级已知参数和设计要求：学生应完成的工作：目前资料收集情况（含指定参考资料）：课程设计的工作计划：任务下达日期 年 月 日完成日期 年 月 日指导教师 （签名）学 生 （签名）说明：1、学院、专业、年级均填全称，如：光电工程学院、测控技术、2003。2、本表除签名外均可采用计算机打印。本表不够，可另附页，但应在页脚添加页码。数据结构与算法课程设计摘要 本文主要针对各种内部排序算法的时间复杂度分析结果只给出

5、了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受，对各种算法比较次数和移动次数的比较，针对各种不同数组如何选择更高效的排序方法，给出一定的指导。各种算法的稳定性也至关重要，对于各种不同类型的数据，各种算法的效果有明显差异，所以针对每种算法，都有不同的数据与之对应，该稳定性表明算法的稳定程度。有效时间则为各种算法针对每组数据实际用掉的计算机时间，可以分析各种排序算法的时间效率。关键字 时间复杂度 有效时间 稳定性 一问题重述 1.1问题描述 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据

6、比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。1.2基本要求 （1）对以下10种常用的内部排序算法进行比较：直接插入排序；折半折入排序；二路插入排序；希尔排序；起泡排序；快速排序；简单选择排序；堆排序；归并排序；基数排序。（2）待排序表的表长不少于100；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。二算法构建 2.1算法思想 所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。当待排序记录的关键字都不相同时，排序结果是惟一的，否则排序结果不惟一。 在待排序

7、的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生改变，则称这种排序方法是不稳定的。 要注意的是，排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。2.1.1插入排序 插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。.直接插入排序(稳定)接插入排序的过程为：在插入第i个记录时，r1,r2,.ri-

8、1已经排好序，将第i个记录的排序码ki依次和r1,r2,.,ri-1的排序码逐个进行比较，找到适当的位置。使用直接插入排序，对于具有n个记录的文件，要进行n-1趟排序。.希尔排序(不稳定)： 希尔(shell)排序的基本思想是：先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取得第二个增量d2d1重复上述的分组和排序，直至所取的增量di=1，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。 一般取d1=n/2，di+1=di/2。如果结果为偶数，则加1，保证di为奇数。

9、希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，其平均时间复杂度为o(n1.3).2.1.2.选择排序 选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。 .直接选择排序(不稳定) 直接选择排序的过程是：首先在所有记录中选出序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换.依次类推，直到所有记录排完为止。 无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需要做n-i次比较，因此，总的比较次数为n(n-1)/2=o(n2)。当初始文件为

10、正序时，移动次数为0；文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为o(n2)。直接选择排序是不稳定的。.堆排序(不稳定) 堆排序是一种树形选择排序，是对直接选择排序的有效改进。n个关键字序列k1,k2,.,kn称为堆，当且仅当该序列满足(ki=k2i且ki=k2i且ki=k2i+1),(1=ik2，则交换k1和k2所在的记录，否则不交换。继续对k2和k3重复上述过程，直到处理完kn-1和kn。这时最大的排序码记录转到了最后位置，称第1次起泡，共执行n-1次比较。 与第一步类似，从k1和k2开始比较，到kn-2和kn-1为止，共执行

11、n-2次比较。 依次类推，共做n-1次起泡，完成整个排序过程。 若文件的初始状态是正序的，一趟扫描即可完成排序。所需关键字比较次数为n-1次，记录移动次数为0。因此，冒泡排序最好的时间复杂度为o(n)。 若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1=i=n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较次数达到最大值n(n-1)/2=o(n2),移动次数也达到最大值3n(n-1)/2=o(n2)。因此，冒泡排序的最坏时间复杂度为o(n2)。 虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均性能比直接插入排序要差得

12、多。冒泡排序是就地排序，且它是稳定的。.快速排序：(不稳定的) 快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 快速排序的具体过程如下： 第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。 第二步，采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。2.1.4归并排序 归并排序是将两个或两个以上的有序子表

13、合并成一个新的有序表。初始时，把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为n的有序表，排序结束。 归并排序是一种稳定的排序，可用顺序存储结构，也易于在链表上实现，对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为o(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是o(nlog2n)。归并排序需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅助空间复杂度为o(n),显然它不是就地排序。五.基数排序设单关键字的每个分量的取值范围均是c0=kj=crd-1(0=j=(const

14、key &y,const key &x);bool operator (const key &y,const key &x);bool operator (const key &y,const key &x); 随机数数据类型class random public: random(bool pseudo = true); int random_integer(int low, int high); double random_real(); private: int reseed(); / re-randomize the seed. int seed, multiplier, add_on;

15、 / constants for use in arithmetic operations; 可排序的顺序表数据类型template class sortable_list:public mylistpublic:sortable_list():mylist()void insertion_sort();void selection_sort();void swap(int low,int high);int max_key(int low, int high);void quick_sort();void recursive_quick_sort(int low, int high);int

16、 partition(int low, int high);void merge_sort();void recursive_merge_sort(int low, int high);void merge(int low, int high);void heap_sort();void insert_heap(const list_entry ¤t, int low, int high);void build_heap();void scan_sort();void insertion_binary();void bubble_sort();void shell_sort();v

17、oid sort_interval(int start, int increment);计算机时间数据类型class timerpublic:timer();double elapsed_time();void reset();private:clock_t start_time;三 算法实现源程序 #include #includesortable_list.h#includetimer.h#includerandom.husing namespace std;sortable_list the_list;sortable_list copy_list;void write_entry(ke

18、y &c)cout (key) c).the_key() ;void help() /帮助函数cout user options are:n help quit (re)fill list n write data write sorted output n 0 insertion sort - project 2p1dn 1 selection sort - project 3p1n 2 shell sort - project 4p2n 3 quick sortn 4 heap sortn 5 insertion, with binary search - project 2p2n 6 s

19、can sort - project 2p3n 7 bubble sort - project 2p4n 8 merge sort - project 7p4n endl;void intro() /介绍函数cout testing program for sorting methods for a contiguous list. endl;help (); void main()intro();int n;random dice;/随机数error_code report; key target; /目标键char command = ;while (command != q & comm

20、and != q) /大循环函数，不退出一直循环执行。cout enter a command of h, q, f, o, d, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, b: command;switch (command) case h: case h:help();break;case d: case d:cout nunsorted list n;the_list.traverse(write_entry);cout endl;break;case o: case o:cout nlast sorted list n;copy_list.traverse(write

21、_entry); /写出数组cout endl;break;case 0: case 1: case 2: case 3: case 4: case 5:case 6: case 7: case 8: case 9: case b: case b: /选择不同的排序函数copy_list = the_list;key:comparisons = 0;key:assignments = 0;timer clock;switch (command) case 0:cout insertion sort ;copy_list.insertion_sort();break;case 1:cout se

22、lection sort ;copy_list.selection_sort();break;case 2:cout shell sort ;copy_list.shell_sort();break;case 3:cout quick sort ;copy_list.quick_sort();break;case 4:cout heap sort ;copy_list.heap_sort();break;case 5:cout insertion sort with bianry search ;copy_list.insertion_binary();break;case 6:cout sc

23、an sort ;copy_list.scan_sort();break;case 7:cout bubble sort ;copy_list.bubble_sort();break;case 8:cout merge sort ;copy_list.merge_sort();break;cout time: clock.elapsed_time() seconds.n /输出运行时间 comparisons: key:comparisons n assignments: key:assignments endl;break;case f: case f:the_list.clear(); /

24、清空表cout how many list entries would you like? n;for (int i = 0; i n; i+) /循环赋予表中数组随机数target = dice.random_integer(0, 10 * n);report = the_list.insert(i, target);if (report = overflow) cout available list space filled up at i entries. endl;break;if (report != success) i-; /更新计数ibreak; / end of outer

25、switch statement / end of outer while statement#include random.h#include #include#includeusing namespace std;int random:reseed() /产生随机数种子函数/*post: the seed is replaced by a pseudorandom successor.*/ seed = seed * multiplier + add_on; return seed;random:random(bool pseudo) /构造函数/*post: the values of

26、seed, add_on, and multiplier are initialized. the seed is initialized randomly only if pseudo = false.*/ if (pseudo) seed = 1; else seed = time(null) % int_max; multiplier = 2743; add_on = 5923;double random:random_real() /产生随机实数函数/*post: a random real number between 0 and 1 is returned.*/ double ma

27、x = int_max + 1.0; double temp = reseed(); if (temp high) return random_integer(high, low); else return (int) (high - low + 1) * random_real() + low;#include key.h#include int key:comparisons = 0;int key:assignments = 0;void key:initialize() /初始化函数comparisons = 0;int key:counter() /计数函数return compar

28、isons;key:key (int x)key = x;key &key:operator =(const key &x) /重载赋值运算符key:assignments+;key = x.key;return *this;bool operator =(const key &x, const key &y)key:comparisons+;return x.the_key() = y.the_key();bool operator !=(const key &x, const key &y)key:comparisons+;return x.the_key() != y.the_key()

29、;bool operator =(const key &x, const key &y)key:comparisons+;return x.the_key() = y.the_key();bool operator =(const key &x, const key &y)key:comparisons+;return x.the_key() (const key &x, const key &y)key:comparisons+;return x.the_key() y.the_key();bool operator (const key &x, const key &y)key:compa

30、risons+;return x.the_key() y.the_key();int key:the_key() constreturn key;四 结果与分析测试数据 测试数据为100个随机数，应该random类，我们可以给表中赋随机数组，可以用于检验各种排序函数的性能。随机数可以在控制台上显示，便于观察。例：产生100个随机数：4.1测试结果 排序后表中数据为：4.2结论分析按平均时间将排序分为四类：（1）平方阶(o(n2)排序 一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶(o(nlgn)排序 如快速、堆和归并排序；（3）o(n1+)阶排序 是介于0和1之间的常数，

31、即01，如希尔排序；（4）线性阶(o(n)排序 如基数排序。各种排序方法比较 简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。影响排序效果的因素 因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：待排序的记录数目n；记录的大小(规模)；关键字的结构及其初始状态；对稳定性的要求；语言工具的条件；存储结构；时间和辅助空间复杂度等。不同条件下，排序方法的选择(1)若n较小(如n50)，可采用直接插入或直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为o(nlgn)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短； 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。 若要求排序稳定，则可选用归并