冒泡排序是一種非常常見的排序演算法。如同水中的一排泡泡，先冒出最大的一個泡泡。再冒出剩餘泡泡中的最大泡泡，依次類推，它的排序規則如下： 1. 從第一個元素開始，比較相鄰的兩個元素，如果後面的小於前面的，交換兩個的位置，一直比較到最後一個 2. 迴圈1中的操作，但已經確定的最大的元素不再參與比較 3. ...
冒泡排序是一種非常常見的排序演算法。如同水中的一排泡泡，先冒出最大的一個泡泡。再冒出剩餘泡泡中的最大泡泡，依次類推，它的排序規則如下：
- 從第一個元素開始，比較相鄰的兩個元素，如果後面的小於前面的，交換兩個的位置，一直比較到最後一個
- 迴圈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));
}
