冒泡排序：它重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。
每經(jīng)過一趟冒泡后，最大的數(shù)會浮到數(shù)組的最頂端(升序)。假設(shè)一個數(shù)組有n個數(shù)，則經(jīng)過n-1趟冒泡后該數(shù)組就會被排好序。
冒泡排序的原理
冒泡排序算法原理如下：
1.比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2.對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
3.針對所有的元素重復以上的步驟，除了最后一個。
4.持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較
冒泡排序過程
假設(shè)有一個逆序數(shù)組5 ,4,3, 2, 1其冒泡排序的過程如下：
算法實現(xiàn)
使用Java實現(xiàn)
public static void bubbleSort(int[] arr){
if(arr == null || arr.length < 2)return;
//一共有l(wèi)ength-1趟冒泡
for(int i=1; i <= arr.length-1; i++){
//每一趟有l(wèi)ength-i次比較
for(int j =0; j<arr.length-i; j++){
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
時間復雜度
在最壞的情況下，就是逆序的時候需要進行n-1次的掃描，每次掃描需要進行n-i次的比較。關(guān)鍵字比較的次數(shù)Cmax = n(n-1)/2 = O(n2), 移動的次數(shù)Mmax = 3n(n-1)/2 = O(n2);
在最好的情況下，就是順序時候只需要1掃描就完成，進行0次交換。Cmin = n-1,
Mmin = 0。
平均時間復雜度O(n2)；
算法穩(wěn)定性
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個元素比較，交換也發(fā)生在這兩個元素之間。所以，如果兩個元素相等，是不會再交換的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法。
