冒泡算法

思路：

因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区中气泡的重量总是大于等于有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。

若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个布尔量exchange，在每趟排序开始前，先将其置为false。若排序过程中发生了交换，则将其置为true。各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。

算法：

void bubblesort(seqlist r)  

  { //r（l..n)是待排序的文件，采用自下向上扫描，对r做冒泡排序  

    int i，j；  

    boolean exchange； //交换标志  

    for(i=1;i<n;i++){ //最多做n-1趟排序  

      exchange=false； //本趟排序开始前，交换标志应为假  

      for(j=n-1;j>=i；j--) //对当前无序区r[i..n]自下向上扫描  

       if(r[j+1].key<r[j].key){//交换记录  

         r[0]=r[j+1]； //r[0]不是哨兵，仅做暂存单元  

         r[j+1]=r[j]；  

         r[j]=r[0]；  

         exchange=true； //发生了交换，故将交换标志置为真  

        }  

      if(!exchange) //本趟排序未发生交换，提前终止算法  

            return；  

    } //endfor(外循环)  

   } //bubblesort  

时间复杂度分析：

（1）算法的最好时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数c和记录移动次数m均达到最小值：

cmin=n-1

mmin=0。

冒泡排序最好的时间复杂度为o(n)。

（2）算法的最坏时间复杂度

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

cmax=n(n-1)/2=o(n2)

mmax=3n(n-1)/2=o(n2)

冒泡排序的最坏时间复杂度为o(n2)。

（3）算法的平均时间复杂度为o(n2)

虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。

（4）算法稳定性

冒泡排序是就地排序，且它是稳定的。

转载：http://blog.csdn.net/xsf50717/article/details/40346927