冒泡排序算法的分析与改进 算法设计.doc

冒泡排序算法的分析与改进 孙伟 （安徽中医学院 医药信息工程学院 09医软一班，安徽合肥，230009） 摘 要： 冒泡排序算法有两个优点：1“编程复杂度”很低，很容易写出代码；2.具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，但当需要排序的数据较多且无序时，冒泡排序算法的时间复杂度较大，比较次数较多，本文提出了一种冒泡排序算法的改进方法，可以大大减少比较的次数，降低算法的时间复杂度。 关键词：交换排序 扫描 稳定 算法 中图分类号：TU 41 文献标识码：A Bubble sort algorithm analysis and improvement SUN Wei (Anhui University of Traditional Chinese Medicine Medical Information Engineering, Hefei 230009, China；) Abstract: Bubble sort algorithm has two advantages:1 “Programming complexity”is very low，and it is easy to write code;2.It has the stability, the stability refers to the original sequence in the same element relative sequence remains to sort sequence, but when the need to sort the data and more disordered, bubble sort algorithm time complexity compared to larger, more often, this paper presents a bubble sort algorithm method, can greatly reduce the number of comparisons, reduce the time complexity of algorithm. Key words：Exchange sort ; Scanning ; stability ; Algorithm  1.概述 冒泡排序简介 冒泡排序法是一种交换排序法，这种方法的基本思想是，将待排序 的元素看作是竖着排列的“ 气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“ 气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“ 轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“ 最轻”的元素就浮到了最高位置；处理二遍之后，“ 次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“ 最轻”元素，所以不必检查。一般地，第i 遍处理时，不必检查第i 高位置以上的元素，因为经过前面i- 1遍的处理，它们已正确地排好序。 1.2 冒泡排序方法 冒泡排序法是一种最简单的排序算法,它和气泡从水中往上冒的情况有些类似。其基本算法如下：对1 至n 个记录，先将第n 个和第n- 1 个记录的键值进行比较，如r[n].keyr[n- 1].key,则将两个记录交换。然后比较第n- 1 个和第n- 2 个记录的关键字； 依次类推， 直到第2 个记录和第1 个记录进行比较交换，这称为一趟冒泡。这一趟是所实现的功能：将键值最小的记录传到了第1 位。然后，再对2 至n 个记录进行同样操作，则具有次小键值的记录被安置在第2 位上。重复以上过程， 每次的移动都向最终排序的目标前进，直至没有记录需要交换为止。具体实现时，可以用一支旗子flag 表示第i 趟是否出现交换。如果第i 趟没有交换，则表示此时已完成排序，因而可以终止。 1.3 冒泡排序过程示例 设待排序的键值为： 25 17 65 13 94 47 41 94 执行冒泡排序的过程如下图所示。其中，第一列为初始键值序列,第二列至第八列依次为各趟排序的结果， 图中用方括号括起来的是当前待排序的无序区。 每一次排序都使有序区扩充了一个气泡，在经过i 次排序之后，有序区中就有i 个气泡， 而无序区中气泡的重量总是大于等于有序区中气泡的重量，整个冒泡排序过程至多需要进行n- 1 次排序。但是,若在某一次排序中未发现气泡位置的交换， 则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则因此冒泡排序过程可在此次排序后终止。在上图的示例中，在第四次(图