氣泡排序演算法

氣泡排序是一個簡單的排序演算法。這個排序演算法是基於比較演算法，其中每對相鄰元件的比較和元素，如果它們不按順序則交換位置。這個演算法是不適合大的資料集，它平均值和最壞情況的複雜性是O(n²)，其中n是專案的排位。

演算法

我們假定列表是n個元素的陣列。我們進一步假設 swap函式，交換給定陣列元素的值。

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

虛擬碼

我們觀察演算法，氣泡排序比較每對陣列元素，除非整個陣列完全是升序排列。這可能會導致幾個複雜的問題，如果陣列不需要更多的交換，因為所有的元素都已經升序順序。

為了緩解這個問題，我們用換一個的標誌變數，它會幫助我們，看是否有交換的發生與否。如果沒有交換的發生，即陣列不需要更多的處理進行排序，它會跳出迴圈。

氣泡排序演算法的虛擬碼可寫成如下 -

procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list[j] > list[j+1] then
            /* swap them */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
   end for
   
end procedure return list

實現

還有一個問題，我們並沒有在原來的演算法及其簡易偽地址，也就是說，在每次疊代後的最高值，位於陣列的結尾。所以，下一次疊代需要不包括已排序的元素。為了這個目的，在我們的實現中限制了內迴圈，以避免已排序值。

要檢視C程式設計語言氣泡排序的實現，請點選這裡