冒泡排序：它重復(fù)地走訪過要排序的元素列，依次比較兩個(gè)相鄰的元素妄痪，如果他們的順序（如從大到小哈雏、首字母從A到Z）錯(cuò)誤就把他們交換過來。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換衫生，也就是說該元素列已經(jīng)排序完成裳瘪。
每經(jīng)過一趟冒泡后，最大的數(shù)會(huì)浮到數(shù)組的最頂端(升序)罪针。假設(shè)一個(gè)數(shù)組有n個(gè)數(shù)彭羹，則經(jīng)過n-1趟冒泡后該數(shù)組就會(huì)被排好序。
冒泡排序的原理
冒泡排序算法原理如下：
1.比較相鄰的元素泪酱。如果第一個(gè)比第二個(gè)大派殷，就交換他們兩個(gè)。
2.對(duì)每一對(duì)相鄰元素做同樣的工作墓阀，從開始第一對(duì)到結(jié)尾的最后一對(duì)毡惜。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)斯撮。
3.針對(duì)所有的元素重復(fù)以上的步驟经伙，除了最后一個(gè)。
4.持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟勿锅，直到?jīng)]有任何一對(duì)數(shù)字需要比較
冒泡排序過程
假設(shè)有一個(gè)逆序數(shù)組5 ,4,3, 2, 1其冒泡排序的過程如下：
算法實(shí)現(xiàn)
使用Java實(shí)現(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;
}
}
}
}
時(shí)間復(fù)雜度
在最壞的情況下帕膜，就是逆序的時(shí)候需要進(jìn)行n-1次的掃描枣氧，每次掃描需要進(jìn)行n-i次的比較。關(guān)鍵字比較的次數(shù)Cmax = n(n-1)/2 = O(n2), 移動(dòng)的次數(shù)Mmax = 3n(n-1)/2 = O(n2);
在最好的情況下垮刹，就是順序時(shí)候只需要1掃描就完成作瞄，進(jìn)行0次交換。Cmin = n-1,
Mmin = 0危纫。
平均時(shí)間復(fù)雜度O(n2)宗挥；
算法穩(wěn)定性
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較种蝶，交換也發(fā)生在這兩個(gè)元素之間契耿。所以，如果兩個(gè)元素相等螃征，是不會(huì)再交換的搪桂；如果兩個(gè)相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個(gè)相鄰起來盯滚，這時(shí)候也不會(huì)交換踢械，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩(wěn)定排序算法魄藕。
