9.4　起泡排序

起泡排序又称冒泡排序,是一种简单的交换排序方法。其基本思想是:依次比较整个序列中相邻的两个记录的关键字,如果逆序（即前一个记录的关键字大于后一个记录的关键字）就交换这两个记录,直到没有逆序的记录为止。

假设有待排序的n个记录存放在数组R[n]中,在使用冒泡排序时,首先将R[1]的关键字与R[2]的关键字进行比较,如果为逆序（即R[1].key＞R[2].key）,就交换这两个记录,若为顺序,则不交换位置,然后再比较R[2]的关键字和R[3]的关键字,依此类推,直到比较R[n－1]与R[n]的关键字后为止。这样的过程称为一趟冒泡排序,其结果是将关键字最大的记录调整到最后一个记录位置上。这样,在第一趟比较结束后,R[n]为关键字最大的记录。然后进行第二趟冒泡排序,再对前n－1个记录重复上述的操作,其结果是将余下的记录中关键字最大的记录调整到第n－1个记录的位置上,即R[n－1]为剩余记录中关键字最大的记录。由此可见,每一趟冒泡排序都会有一个无序区中的最大记录排到无序区的最后一个位置。这样在经过n－1趟排序之后,整个记录序列就变成有序序列。

冒泡排序算法描述如下。

由上述算法可知,冒泡排序必然要经过n－1趟排序,即使在某趟排序之后序列已经变成有序的序列,排序也要继续进行下去,直到进行了n－1趟之后才结束排序过程。为了保证冒泡排序算法在待排序列为有序的情况下不再继续进行排序,对算法进行如下改进。

【算法分析】

（1）稳定性　由于在排序的过程中,是相邻的两个记录之间进行交换,由交换的条件可知冒泡排序算法是稳定的排序算法。

（2）空间复杂度　在排序的过程中,使用了一个中间变量,即辅助空间为1个单位,故而空间复杂度为O（1）。

（3）时间复杂度　最好的情况为:初始记录序列为“正序”序列,只需进行一趟排序,记录移动次数为0,关键字间比较次数为n－1。最坏的情况为:初始记录序列为“逆序”序列,则进行n－1趟排序,每一趟中的比较和交换次数将达到最大,即冒泡排序的最大比较次数为（i－1）＝n（n－1）/2,最大移动次数为3×（i－1）＝3n（n－1）/2。一般情况下,比较次数≤n（n－1）/2,移动次数≤3n（n－1）/2,因此其时间复杂度为O（n²）。

【例9－3】　设待排序的9个记录的关键字序列为{312,126,272,226,8,165,123,12,28},使用冒泡排序算法进行的排序过程如图9－1所示。

图9－1　冒泡排序的过程