排序演算法--冒泡排序(一)

冒泡排序(Bubble Sort)

冒泡排序是一種簡單的排序演算法。它適合小規模數據的排序,並且其效率比較低,但是作為一個入門的演算法,還是值得學習的。

1. 什麼是冒泡排序？

冒泡排序是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。

2. 演算法描述（此處以正序為例）

比較相鄰的兩個數，如果第一個數比第二個數大，則兩數交換。
對之後的相鄰元素進行同樣的工作，從開始到最後一對，這樣進行一次排序後，數據的最後一位會是最大值，第一次循環進行的次數為 arr.length-1。
之後對所有的元素重複以上的步驟，且以後每次循環的次數為arr.length-1-i （i為循環第幾次，i 從零開始）；
重複上述步驟，直到排序完成

3. 代碼實現

public void BubbleSort(int[] arr){ for(int i=0;i<arr.length-1;i++){ for(int j=0;j<arr.length-1-i;j++){ if(arr[j]>arr[j+1]){ //相鄰兩個元素作比較，如果前面元素大於後面，進行交換 int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } } }

4. 冒泡排序複雜度分析

分析一下它的時間複雜度。當最好的情況，也就是要排序的表本身就是有序的，那麼我們比較次數，那麼可以判斷出就是n-1次的比較，沒有數據交換，此時時間複雜度為O(n)。當最壞的情況，即待排序是逆序的情況，此時需要比較 $sum_{i=2}^{n}{i-1}=1+2+3+cdotcdotcdot+(n-1)=frac{n(n-1)}{2}$ 次，此時時間複雜度為 $O(n^{2})$ 。