基本思想
??????冒泡排序是一種 交換排序大溜，它的基本思想是：兩兩比較相鄰記錄的關(guān)鍵字织中，如果反序則交換苗缩，直到?jīng)]有反序的記錄為止崭参。
冒泡排序初級版
??????嚴(yán)格意義上來說這版不是標(biāo)準(zhǔn)的冒泡排序算法，因為他不滿足“兩兩比較 相鄰 記錄”的冒泡排序思想慰于，它更應(yīng)該是最簡單的交換排序而已钮科。
??????它的思路是：讓每一個關(guān)鍵字都和后面的每一個關(guān)鍵字比較，如果大則交換婆赠，這樣第一位置的關(guān)鍵字在一次循環(huán)后一定變成最小值绵脯。
void bubbleSort(int[] array) {
int length = array.length;
for (int i = 0; i < length - 1; i++) {
for (int j = i + 1; j < length; j++) {
if (array[i] > array[j]) {
swap(array, i, j);
}
}
}
}
??????假設(shè)待排序的關(guān)鍵字序列為{9,1,5,8,3,7,4,6,2}，當(dāng)i=0時休里，9與1交換后在第一位置的1與后面的關(guān)鍵字比較都小蛆挫，因此它為最小值；當(dāng)i=1時妙黍，第二位置先由9交換成5悴侵，再由5交換成3，由3換成2拭嫁，完成了第二小的數(shù)字交換可免。后面的數(shù)字變換類似。
缺點：觀察上圖可以看出做粤，在排序好1和2的位置后對其余的關(guān)鍵字排序沒有什么幫助巴元，所以這個算法的效率是非常低的。
正宗的冒泡排序
void bubbleSort(int[] array) {
int length = array.length;
for (int i = 1; i < length; i++) {
// 注意是j從后往前循環(huán)
for (int j = length - 1; j >= i; j--) {
if (array[j-1] > array[j]) {
swap(array, j - 1, j);
}
}
}
}
??????假設(shè)待排序的關(guān)鍵字序列為{9,1,5,8,3,7,4,6,2}驮宴，當(dāng)i=1時逮刨，變量j由8反向循環(huán)到1，逐個比較堵泽，將較小值交換到前面修己，直到最后找到最小值放置在了第一個位置。如圖所示迎罗，當(dāng)i=1睬愤、j=8時，發(fā)現(xiàn)6大于2-交換他們的位置纹安，j=7時尤辱，4大于2-交換位置······直到j(luò)=2時由于1小于2所以不交換；j=1時9大于1進行交換厢岂，最終得到最小值1放置在第一個位置上光督。
??????整個循環(huán)過程中不止將最小值放置在了第一位，還將較小值提到了前面塔粒，相較于之前的算法结借，這一版明顯要有進步。
圖中較小的數(shù)字如同氣泡般慢慢浮到上面卒茬，因此命名為冒泡算法船老。
冒泡排序的優(yōu)化
??????如果待排序的字段已經(jīng)是一個局部有序的序列咖熟，那么很多循環(huán)操作都是多余的。比如當(dāng)待排序序列是{2,1,3,4,5,6,7,8,9}時柳畔，當(dāng)i=1時交換了2和1馍管，但是程序仍然不依不饒的將i=2到8以及每個循環(huán)中的j循環(huán)都執(zhí)行了一遍，盡管沒有交換數(shù)據(jù)薪韩，但是大量的比較操作還是多余了咽斧。
void bubbleSort(int[] array) {
int length = array.length;
// flag用來作為標(biāo)記--可以避免已經(jīng)有序情況下的無意義的循環(huán)
boolean flag = true;
for (int i = 1; i < length && flag; i++) {
flag = false;
for (int j = length - 1; j >= i; j--) {
if (array[j - 1] > array[j]) {
swap(array, j - 1, j);
flag = true;
}
}
}
}
冒泡排序的時間復(fù)雜度分析
??????最好情況下，排序表本身是有序的躬存，根據(jù)優(yōu)化后的代碼需要比較（n-1）次张惹，沒有數(shù)據(jù)交換，時間復(fù)雜度O(n)
??????最壞情況下岭洲，排序表本身是逆序的宛逗，需要比較1+2+3+······+(n-1)次，就是n(n-1)/2次比較盾剩，并作等數(shù)量級的記錄移動雷激，時間復(fù)雜度為O(n^2)
