冒泡排序是一種非常常見的排序算法。如同水中的一排泡泡，先冒出最大的一個泡泡。再冒出剩餘泡泡中的最大泡泡，依次類推，它的排序規則如下：
- 從第一個元素開始，比較相鄰的兩個元素，如果後面的小于前面的，交換兩個的位置，一直比較到最後一個
- 循環1中的操作，但已經确定的最大的元素不再參與比較
- 直到不确定大小順序的元素剩餘兩個，然後對這兩個進行比較，然後結束循環
排序圖示（圖檔來源網絡）
java實作
用java實作一個簡單的冒泡排序。為了便于了解，在尋找到第一個最大元素完成後，稱之為第一趟，依次類推，可以發現一共需要n-1趟
public void bubbleSort() {
int[] array = {6, 2, 5, 3};
for (int i = 0; i < array.length - 1; i++) {// 需要排序的趟數
for (int j = 0; j < array.length - i - 1; j++) {// 每一趟需要比較的次數
if (array[j + 1] < array[j]) {
int variable = array[j + 1];
array[j + 1] = array[j];
array[j] = variable;
}
}
System.out.println("第" + (i + 1) + "趟排序後的結果：" + Arrays.toString(array));
}
System.out.println("最終的排序結果：" + Arrays.toString(array));
}
console
第1趟排序後的結果：[2, 5, 3, 6]
第2趟排序後的結果：[2, 3, 5, 6]
第3趟排序後的結果：[2, 3, 5, 6]
最終的排序結果：[2, 3, 5, 6]
排序過程分析
第一趟排序
排序前：[6, 2, 5, 3]
排序後：[2, 5, 3, 6]
6與2比較，然後互換位置，然後與5比較，互換位置，最後與3比較，互換位置,此時6在最後的位置，确定最大值6，一共比較3次
第二趟排序
排序前：[2, 5, 3, 6]
排序後：[2, 3, 5, 6]
2與3比較，位置不變，然後5與3比較，然後互換位置，因為6的位置已經确定，是以5與6不再比較，一共比較2次
第三趟排序
排序前：[2, 3, 5, 6]
排序後：[2, 3, 5, 6]
2與3比較，位置不變，5,6的位置已經确定，是以不再比較，一共比較1次
由上面的分析可以看出，一共進行了1+2+...+n-1次比較。也就是n(n-1)/2次,即(N^2 - n)/2次,去除對結果影響不大的N^2 - n中的-n,以及系數0.5，得出時間複雜度為 O(N^2) (注：此處的時間複雜度自己尚未完全了解，希望明白的朋友可以給予解答)
優化
上述的排序還存在優化的空間，如果本來就是一列從小到大的數，按上述操作，很容易造成資源浪費。最理想的情況下，對于一列從小到大的數，進行n次比較，即可得出結果。如果某一趟排序中，沒有出現互換操作，即表示已經得到了正确的結果，此時可以結束排序，示例如下：
public void bubbleSort() {
int[] array = {6, 2, 5, 3};
for (int i = 0; i < array.length - 1; i++) {// 需要排序的趟數
boolean flag = false;// 預設不存在位置交換
for (int j = 0; j < array.length - i - 1; j++) {// 每一趟需要比較的次數
if (array[j + 1] < array[j]) {
flag = true;// 存在位置交換，修改flag為true
int variable = array[j + 1];
array[j + 1] = array[j];
array[j] = variable;
}
}
if (!flag) {
break;// 不存在位置交換 跳出循環
}
}
System.out.println("最終的排序結果：" + Arrays.toString(array));
}
作者：zhaoguhong(趙孤鴻)
出處：http://www.cnblogs.com/zhaoguhong/
個人部落格：http://www.zhaoguhong.com
本文版權歸作者和部落格園共有，轉載請注明出處