冒泡排序算法

冒泡排序是一個簡單的排序算法。這個排序算法是基於比較算法,其中每對相鄰元件的比較和元素,如果它們不按順序則交換位置。這個算法是不適合大的數據集,它平均值和最壞情況的複雜性是O(n2),其中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編程語言冒泡排序的實現,請點擊這裏