扫码获取更多资源

●冒泡排序

冒泡排序(Bubble Sort)是交换排序中最简单的一种排序方法，需要解决两个关键问 题：一是如何确定待排序记录的范围，使得已经位于最终位置的记录不参与下一趟排序； 二是如何判别冒泡排序结束。

将n个待排序记录序列站，『 …，琮｝划分成有序区和无序区，初始时有序区为空，无 序区包括所有待排序的记录。设有序区右边界为bound,存储有序区最后一个记录的位置， 即有序区记录为. rbound ；无序区中每趟待排序记录为rbound+1.. rno

对无序区从后向前依次将相邻记录的关键字进行比较，如果反序则交换，从而使得关键 字小的记录向前移，关键字大的记录向后移。重复执行该过程，直到无序区中没有反序记录 为止。为了提高排序效率，设置标志tag： tag = 0表示在一趟排序过程中进行过交换记录操 作；tag=l表示在一趟排序过程中没有进行过交换记录操作，提前结束冒泡排序。

分割待排序记录

子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序 列.这样才能有效地保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不 是局部有序。接下来的问题是增量应该如何取？到目前为止尚未有人求得一个最好的增量 序列。希尔(D. L. shell)最早提出的方法是：山=|_n/2」,&+1 =|_出/2丄且没有除1之外的公 因子，并且最后一个增量必须等于10开始时增量的取值较大，每个子序列中的记录个数较 少，并且提供了记录跳跃移动的可能，排序效率较高；后来增量逐步缩小，每个子序列中的 记录个数增加，但已基本有序，效率也较高。

例9-3待排序记录关键字序列为{13, 49, 38, 65, 97, 76, 27,泡排序的过程(方括号括起来的为有序区)。

算法描述

假设待排序记录个数为no当初始文件记录为正序时，只需要进行一趟排序，总关键字 比较次数为n-1,且不移动记录。当初始文件记录为反序时，需要进行n-1趟排序，总关 键字比较次数为n(n-l)/2,且作等量级的记录移动。因此算法9-3的时间复杂度为()(子)。

冒泡排序只需要一个记录的辅助空间，用来作为记录交换的暂存单元，因此算法9-3的 空间复杂度为0(1)。

算法9-3是一种稳定的排序方法。该方法简单且容易实现，适用于待排记录序列基本 有序，或待排记录数目较少的场合。

联系我们：