一、算法基礎
1.1 什么是冒泡排序
冒泡排序是一種簡單直觀的比較排序算法。它重復地走訪待排序的數列,依次比較相鄰兩個元素,如果順序錯誤就交換它們,直到沒有元素需要交換為止。
1.2 基本思想
- 比較相鄰元素:從頭開始,兩兩比較相鄰元素
- 交換位置:如果前一個元素大于后一個元素,則交換位置
- 重復操作:每完成一次迭代,最大的元素會"冒泡"到數組末尾
- 多次迭代:重復以上步驟,每次排除已排好序的末尾元素
1.3 時間復雜度
- 最好情況:O(n),當數組已經排好序
- 最壞情況:O(n2),當數組逆序排列
- 平均情況:O(n2)
二、冒泡排序的分類
2.1 標準冒泡排序
標準版本每次將最大元素冒泡到末尾:
- 外層循環:控制排序輪數,最多n-1輪
- 內層循環:控制每輪比較次數,逐漸減少
- 無優化:即使數組已排序仍會執行全部循環
2.2 優化冒泡排序
通過標記變量檢測一輪比較中是否有交換發生:
- 設置標記:初始假設本輪無交換
- 發生交換:更新標記變量
- 提前終止:若一輪比較無交換發生,則排序完成
三、冒泡排序實現
3.1 標準實現
public class BubbleSort {/*** 標準冒泡排序算法* @param arr 待排序數組*/public static void bubbleSort(int[] arr) {int n = arr.length;// 外層循環控制排序輪數for (int i = 0; i < n - 1; i++) {// 內層循環進行相鄰元素比較和交換// 每輪結束后,最大的i+1個元素已經排好序for (int j = 0; j < n - i - 1; j++) {// 如果當前元素大于下一個元素,交換它們if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}
}
3.2 優化實現
public class OptimizedBubbleSort {/*** 優化版冒泡排序算法* @param arr 待排序數組*/public static void bubbleSort(int[] arr) {int n = arr.length;boolean swapped;// 外層循環控制排序輪數for (int i = 0; i < n - 1; i++) {swapped = false;// 內層循環進行相鄰元素比較和交換for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交換元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;// 標記發生了交換swapped = true;}}// 如果沒有發生交換,說明數組已經有序,提前結束if (!swapped) {break;}}}
}
3.3 雙向冒泡排序(雞尾酒排序)
public class CocktailSort {/*** 雙向冒泡排序(雞尾酒排序)算法* @param arr 待排序數組*/public static void cocktailSort(int[] arr) {int left = 0;int right = arr.length - 1;boolean swapped;while (left < right) {swapped = false;// 從左向右,將最大元素冒泡到右側for (int i = left; i < right; i++) {if (arr[i] > arr[i + 1]) {int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;swapped = true;}}// 如果沒有交換,數組已經有序if (!swapped) {break;}right--; // 最大元素已經到位,縮小右邊界swapped = false;// 從右向左,將最小元素冒泡到左側for (int i = right; i > left; i--) {if (arr[i] < arr[i - 1]) {int temp = arr[i];arr[i] = arr[i - 1];arr[i - 1] = temp;swapped = true;}}// 如果沒有交換,數組已經有序if (!swapped) {break;}left++; // 最小元素已經到位,縮小左邊界}}
}
四、算法分析與優化
4.1 理論推導
冒泡排序的工作原理可以用以下數學表達式描述:
- 比較次數:(n-1) + (n-2) + ... + 1 = n(n-1)/2
- 最大交換次數:同上 n(n-1)/2
- 元素移動次數:最多3×n(n-1)/2(每次交換需要3次移動)
4.2 優化策略
- 提前終止優化:如前述,檢測是否有交換發生
- 記錄最后交換位置:每輪記錄最后一次交換的位置,下一輪只需掃描到該位置即可
- 奇偶交替掃描:類似雞尾酒排序,減少"烏龜"(小元素靠后)的情況
public class EnhancedBubbleSort {/*** 記錄最后交換位置的優化冒泡排序* @param arr 待排序數組*/public static void bubbleSort(int[] arr) {int n = arr.length;int lastSwappedIndex = n - 1;int newLastSwappedIndex;while (lastSwappedIndex > 0) {newLastSwappedIndex = 0;for (int i = 0; i < lastSwappedIndex; i++) {if (arr[i] > arr[i + 1]) {// 交換元素int temp = arr[i];arr[i] = arr[i + 1];arr[i + 1] = temp;// 記錄最后交換的位置newLastSwappedIndex = i;}}// 更新下一輪排序的終止位置lastSwappedIndex = newLastSwappedIndex;}}
}
五、完整示例程序
public class BubbleSortDemo {public static void main(String[] args) {// 測試數據int[] arr = {64, 34, 25, 12, 22, 11, 90};System.out.println("原始數組: ");printArray(arr);// 執行優化版冒泡排序optimizedBubbleSort(arr);System.out.println("\n排序后數組: ");printArray(arr);}/*** 優化的冒泡排序實現*/public static void optimizedBubbleSort(int[] arr) {int n = arr.length;boolean swapped;for (int i = 0; i < n - 1; i++) {swapped = false;for (int j = 0; j < n - i - 1; j++) {// 如果當前元素大于下一個元素,交換它們if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);swapped = true;}}// 如果沒有發生交換,數組已經有序if (!swapped) {System.out.println("提前結束于第 " + (i + 1) + " 輪");break;}}}/*** 交換數組中兩個元素*/private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}/*** 打印數組*/private static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}
}
六、總結
冒泡排序是一種經典的排序算法,其特點如下:
6.1 優點
- 實現簡單:代碼直觀易懂,適合教學使用
- 穩定性好:相等元素不會改變相對順序
- 原地排序:不需要額外空間
- 自適應性:對于部分有序數據效率較高
6.2 缺點
- 效率低下:平均時間復雜度為O(n2)
- 比較次數多:即使數據已經有序,基本版本仍需大量比較
6.3 適用場景
- 小規模數據:元素數量較少時表現尚可
- 教學演示:算法思想簡單直觀
- 接近有序數據:優化版本在這種情況下效率較高
冒泡排序雖然在大規模數據中效率不高,但其思想簡單,實現容易,是學習排序算法的良好起點。在實際應用中,可根據數據特性選擇更高效的排序算法,如快速排序、歸并排序等。