基于turboc冒泡排序和其改进算法

《基于turboc冒泡排序和其改进算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于TurboC的冒泡排序及其改进算法 摘 要：冒泡排序是计算机程序设计中比较典型的简单排序算法。本文阐述了冒泡排序算法及其优化算法的基本思想和实现方法，分析和比较了优化前后的时间复杂度和空间复杂度及其稳定性，指出了优化冒泡排序算法在效率及性能方面的优越性。关键词：程序设计；冒泡排序法；标志变量法；复杂度分析中图分类号：TP301.6 文献标识码：A   文章编号:9496(2008)01-0000-00    引言：排序[1]是计算机程序设计中的一种重要运算，其功能是将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。通过排序可以进行快速查找。排序分

2、为内部排序和外部排序，其中在内部排序中，比较典型的简单算法有冒泡排序、插入排序和选择排序，这三种算法在平均及最差情况下的时间复杂度皆为O(n2)。但在某些情况下这些最简单的算法可能是最好的算法。本文主要就冒泡排序[3]的算法及其改进算法做以讨论，分析了在不同情况下的时间复杂度和空间复杂度，并给出了其设计思想和在TurboC平台上的具体实现。   1.冒泡排序的基本思想   将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i]的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上“飘浮”。如此反复进行

3、，直到最后任何两个气泡都是轻者在上，重者在下为止。一般地，第i遍处理时，不必检查第i个位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。即就是在一组待排序的数据中，两两比较数据的大小，发现两个记录的排序次序相反时就交换位置，直到没有反序的记录为止。也就是说它重复地走访过要排序的序列，一次比较两个项目，如果他们的顺序错误就把他们交换过来。走访序列的工作是重复地进行直到没有再需要做交换动作，该序列已经排序完成。一趟冒泡，至少可以把值最大的元素送到最后位置(或最上边)；当然也可以倒过来做，把值小的元素向前移或向下移，一趟冒泡，至少可以把值最小的元素送到最前面的位

4、置(或最下边)。   2.冒泡排序算法的实现(升序)   2.1算法1：未优化的算法流程图（如图1），具体算法实现见附1                    图1未优化的算法流程图    以上无序的数据放在区域R[n]中。第一趟从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1]

5、关键字最小的记录被放在最高位置R[1]上。第二趟扫描R[2…n]。扫描完毕时，“次轻”的气泡飘浮到R[2]的位置上……。最后，经过n-1 趟扫描可得到有序区R[1..n]。其中第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[1…i]变为新的有序区。   2.2算法2：改进的算法（标志变量法）   因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以整个

6、冒泡排序过程至多需要进行n-1趟排序。若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。表明上一轮结束时已排好序，此时可以跳出循环，而不必再继续循环，从而使外循环的次数可能减少，提高了排序的效率。所以可以通过添加一个布尔型标志变量[2]的方法来控制循环的执行。   为此，在下面图2给出的算法中，引入一个布尔量exchange，在每趟排序开始前，先将其置为FALSE。若排序过程中发生了交换，则将其置为TRUE。各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一

7、趟排序。（具体算法实现见附2）                     图2 优化后算法流程图    3.算法分析与比较   时间复杂度是指运行完一个程序所需要的时间，空间复杂度是指运行完一个程序所需要的内存大小。评价一个算法的好坏，主要分析它的时间复杂度和空间复杂度[1]，当二者发生冲突的时，往往倾向于时间复杂度。冒泡排序算法的优点是比较容易理解，且当原始数据大体符合要求的次序时，运算速度较快。每趟结束时，不仅能挤出一个最大值到最后面位置或挤出一个最小值到最前面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。当