7.4 泡排序★2◎3

7.4 冒泡排序★2◎3

　　先来看看待排序列一趟冒泡的过程：设1<j≤n，r[1]，r[2]，…，r[j]为待排序列，通过两两比较、交换，重新安排存放顺序，使得r[j]是序列中关键码最大的记录。一趟冒泡方法为：
　　①i=1；设置从第一个记录开始进行两两比较；
　　②若i≥j，一趟冒泡结束；
　　③比较r[i].key与r[i+1].key，若r[i].key≤r[i+1].key，不交换，转⑤；
　　④当r[i].key>r[i+1].key时，r[0]=r[i]；r[i]=r[i+1]；r[i+1]=r[0]；将r[i]与r[i+1]交换；
　　⑤i=i+1；调整对下两个记录进行两两比较，转②。
　　对n个记录的表，第一趟冒泡得到一个关键码最大的记录r[n]；第二趟冒泡对n-1个记录的表，再得到一个关键码最大的记录r[n-1]；如此重复，直到得到n个记录按关键码有序的表。
　　对于序列｛6，3，5，9，7｝，用冒泡法排序的过程如下：

　　【效率分析】
　　空间效率：仅用了一个辅助单元。
　　时间效率：最多进行n-1趟冒泡，对i个记录的表进行一趟冒泡需要i-1次关键码比较：

　　最好情况：待排序列已有序，不需移动，只进行一趟比较，比较次数为n-1次。
　　最坏情况：待排序列逆序，每次比较后要进行3次移动：