c语言程序设计(排序算法)

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第四章程序设计结果 9附录 9参考文献 13引言伴随着社会的发展，数据也变得越来越庞大。如何将庞大的数据进行很好 的排序，使用户更加方便的查找资料，成了一件越来越重要的问题。对于程序员 来说，

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

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

4、故名。冒泡排序（BubbleSort ）的基本概念是：依次比较相邻的两个数，将小数 放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继 续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的 数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第 3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一 直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒 数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此 下去，重复以上

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

6、序区为空。 第1趟排序 在无序区R仁n中选出关键字最小的记录 Rk，将它与无序区 的第1个记录R1交换，使R1.1和R2.n分别变为记录个数增加1个的新有序区和记录个数减少1 个的新无序区。第i趟排序 第i趟排序开始时，当前有序区和无序区分别为R1.i-1和R（1< i < n-1）。该趟排序从当前无序区中选出关键字最小的记录Rk，将它与无序区的第1个记录R交换，使R1.i和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新 无序区。这样，n个记录的文件的直接选择排序可经过 n-1趟直接选择排序得到有序结果。选择排序法的第一层循环从起始元素开始选到倒数第二个元素，主要是在每

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

8、方法。插入算法把要排序的 数组分成两部 分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个 空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第 一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排 序的文件中适当位置上，直到全部插入完为止。1从有序数列和无序数列a2,a3，an开始进行排序；2.处理第i个元素时（i=2,3，n），数列a1,a2，ai-1是已有序 的，而数列ai,ai+1 ，an是无序的。用ai与ai-1 ，a i-2，al进行比 较，找出合适的位

9、置将ai插入；3重复第二步，共进行n-i次插入处理，数列全部有序。第二章概要设计2.1冒泡排序在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对 相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每 当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。for(i=0;i<10;i+)第一轮循环，输入十个数据。scanf( “%d，&ai);printf( “n ” );for(j=0;j<9;j+)挨个判断输入的书的大小，第二轮循环for(i=0;i<9-j;i+)if(ai>ai+1t=ai;进行数的调换，把大的数据

10、调到后面。ai=ai+1;ai+1=t;2.2选择排序简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置，从而减少排序所需的循环次数。改进后对 n个数据进行排序，最多只需进行n/2趟循环即i=lpn=lO;t e m戸=列j) alj)-a(i) aflj-tamp min >0ji+-为数组a的元素个数void select_sort(i nt a,i nt n)/n/进行N-1轮选择for(i nt i=0; i<n-1; i+) int min_in dex = i;/ 找出第i小的数所在的位置for(i

11、nt j=i+1; j< n; j+)if(aj < amin_in dex)min_i ndex = j;/ 将第i小的数，放在第i个位置；如果刚好，就不用交换if( i != min_i ndex)int temp = ai;ai = amin_in dex;amin_i ndex = temp;2.3插入排序将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第 2个记录逐个进行插入，直至整个序列有序为止3A-r34>3AJ5从数组中的第二个元素开始int temp;for (i nt i = 1

12、; i < len gth; +i) /temp = arri; /记录当前的元素int j = i - 1;while (j >= 0 && temp < arrj) /将当前元素与之前的已经排序好的序列元素进行挨个比较arrj + 1 = arrj; /已经排序好的序列整体向后移动T；arrj + 1 = temp; /插入当前的元素第三章程序的比较及其应用3.1时间复杂度冒泡排序算法的最差时间复杂度为 0(n2)，平均时间复杂度为0(n2)。选 择排序算法的最差时间复杂度为 0(n2)，平均时间复杂度为0(n2)。插入排序算法 的最差时间复杂度为0(n2

13、)，平均时间复杂度为0(n2)。冒泡排序和插入排序时间 复杂度最好的情况下是 0(n),而选择排序时间复杂度最好的情况下是0(n2)。从时间复杂度比较来看。选择排序的时间复杂度在以下情况下是没有冒泡排序和插 入排序的好。3.2空间复杂度冒泡排序，选择排序，以及插入排序是空间复杂度都是0(1)。从空间复杂度来看，三者也没有什么可以区分开来的。并不能直观的看出优劣。3.3稳定程度冒泡排序和插入排序的稳定程度都是比较稳定的，只有选择排序是不稳 定的。那么综合上面的比较来看，选择排序是最不好的，而冒泡排序以及插入排 序是比较好的。冒泡排序是最慢的，但是也是最容易懂得。插入排序是比较快的， 但是对于自身

14、的能力有一定的要求。当然，这只是相对而言3.4应用及其改进三种排序算法都可以应用于一些简单排列数据的程序。也可以作为C语言初学者的练手的课题。对于我们学习C语言也是一个不小的帮助。同时可以 加深我们对于循环和数组的理解及其应用。 同时我们可以对冒泡排序进行一点点 的改进，使其更加的完善。冒泡算法的改进，当排序的数据比较多时排序的时间会明显延长。改进 方法：快速排序：具体做法：任意选取某一记录（通常取第一个记录），比较其 关键字与所有记录的关键字，并将关键字比它小的记录全部放在它的前面，将比它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记 录所在的分界点分为两部分，然后分别

15、对这两部分进行快速排序，直至排序完。 在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换， 在传统的冒泡排序算法及近年来的一些改进的算法中，只记录一趟扫描有无数据 交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息， 可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理， 称之为局部 冒泡排序。局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同。由于局部冒泡排序和冒泡排序的数据移动次数总是相同的， 而局部冒泡排序所需关键字的比较次 数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数

16、上对冒泡排序 有所改进，当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销， 而当数据量较大时，局部冒泡排序的时间性能则明显优于冒泡排序。第四章 程序设计结果插入排序算法的结果选择排序算法的结果冒泡排序算法的结果附录冒泡排序：#i nclude<stdio.h>void mai n()int a10;Int i,j,t;printf( “ in put 10 nu mbers :n”);for(i=0;i<10;i+) scanf( “%d，&ai);printf(“n ”)；for(j=0;j<9;j+)for(i=0;i<9-j;i+)if(a

17、i>ai+1t=ai;ai=ai+1;ai+1=t;printf(“ the sorted nu mbers :n”printf(“%d ,ai);printf(“n ”)；选择排序：#i nclude<stdio.h>#i nclude<stdlib.h>#defi ne N 8void select_sort(i nt a,i nt n);/选择排序实现为数组a的元素个数void select_sort(i nt a,i nt n)/n/ 进行N-1轮选择for(i nt i=0; i<n-1; i+)int min_in dex = i;/ 找出第i小

18、的数所在的位置for(i nt j=i+1; j< n; j+)if(aj < amin_in dex)min_i ndex = j;/ 将第i小的数，放在第i个位置；如果刚好，就不用交换if( i != min_i ndex)int temp = ai;ai = amin_in dex;amin_i ndex = temp;int mai n()int numN = 89, 38, 11, 78, 96, 44, 19, 25;select_sort (num, N);for(i nt i=0; i<N; i+)prin tf("%d ", nu mi);prin tf("n&qu