c语言程序设计（排序算法）.doc

《c语言程序设计（排序算法）.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学号2014-2015学年第2学期《高级语言程序设计》课程设计报告题目：排序算法专业：班级：：指导教师：成绩：计算机与信息工程系2015年3月26日目录引言1需求分析1第一章程序容及要求11.1冒泡排序11.2选择排序21.3插入排序3第二章概要设计42.1冒泡排序42.2选择排序52.3插入排序6第三章程序的比较及其应用73.1时间复杂度73.2空间复杂度73.3稳定程度73.4应用及其改进8第四章程序设计结果8附录9参考文献12引言伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员来说，这将是一个挑战

2、。经常查找资料的朋友都会知道，面对海量的资料，如果其查找资料没有进行排序，那么其查找资料将会是一家非常痛苦的事情。针对这一问题，我们自此通过一个课程设计来解决它。理论上排序算法有很多种，不过本课程设计只涉及到三种算法。这三种算法包括：冒泡排序，选择排序，直接插入排序。本课程设计通过对这三种算法的运行情况进行对比，选择最优秀的算法出来。希望通过我的努力能解决一些问题，带来一些方便。需求分析本课程题目是排序算法的实现，由于各方面的原因，本科程设计一共需要设计三种排序算法。这三种算法包括：冒泡排序，选择排序，直接插入排序。三种排序算法各有独到之处，因此我们要通过各种调试分析来比较其优劣长短。由

3、于使用的调试软件及操作系统不一样。因此个别程序在不同的软件上可能会报错。本课程软件运行的的操作系统为Windows764位操作系统。所使用的软件为MicrosoftVisualC++6.0以及TurboC2.0第一章程序容及要求1.1冒泡排序冒泡排序（BubbleSort，译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。冒泡排序（BubbleSort）的基本概念

4、是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。用二重循环实现，外循环变量设为i，

5、循环变量设为j。假如有10个数需要进行排序，则外循环重复9次，循环依次重复9，8，...，1次。每次进行比较的两个元素都是与循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i,j的值依次为1,2,...10-i。冒泡排序算法的性能1.2选择排序每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法。基本思想:n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：①初始状态：无序区为R[1..n]，有序区为空。②第1趟排序在无序区R[1..

6、n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。……③第i趟排序第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进入的第二层循

7、环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换1.3插入排序有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法--插入排序法,插入排序的基本操作就是将一个