冒泡算法

思路：

因為每一趟排序都使有序區增加了一個氣泡，在經過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