冒泡排序算法原理與Java實現¶
在編程中，排序是一項基礎且常見的任務。冒泡排序（Bubble Sort）是最簡單的排序算法之一，其核心思想是通過重複比較相鄰元素並交換位置，使較大的元素“冒泡”到數組末尾（升序排序時），或較小的元素“冒泡”到數組開頭（降序排序時）。
排序步驟解析¶
以數組 [5, 2, 9, 1, 5] 爲例，演示升序排序過程：
-
第一輪（未排序部分：
[5,2,9,1,5]）
- 比較5和2：5 > 2，交換 →[2,5,9,1,5]
- 比較5和9：5 < 9，不交換
- 比較9和1：9 > 1，交換 →[2,5,1,9,5]
- 比較9和5：9 > 5，交換 →[2,5,1,5,9]
- 結果：最大元素9已“冒泡”到末尾，未排序部分變爲[2,5,1,5] -
第二輪（未排序部分：
[2,5,1,5]）
- 比較2和5：2 < 5，不交換
- 比較5和1：5 > 1，交換 →[2,1,5,5]
- 比較5和5：5 = 5，不交換
- 結果：第二大元素5已“冒泡”到倒數第二位，未排序部分變爲[2,1,5] -
第三輪（未排序部分：
[2,1,5]）
- 比較2和1：2 > 1，交換 →[1,2,5]
- 比較2和5：2 < 5，不交換
- 結果：第三大元素5已“冒泡”到倒數第三位，未排序部分變爲[1,2] -
第四輪（未排序部分：
[1,2]）
- 比較1和2：1 < 2，不交換
- 結果：排序完成，數組變爲[1,2,5,5,9]
Java代碼實現¶
public class BubbleSort {
/**
* 冒泡排序算法實現（升序）
* @param arr 待排序的數組
*/
public static void bubbleSort(int[] arr) {
// 外層循環：控制排序輪數（最多n-1輪）
for (int i = 0; i < arr.length - 1; i++) {
boolean swapped = false; // 優化標記：本輪是否發生交換
// 內層循環：控制每輪比較次數（已排好序的元素無需再比較）
for (int j = 0; j < arr.length - 1 - i; 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;
}
}
}
public static void main(String[] args) {
// 測試數組
int[] arr = {5, 2, 9, 1, 5};
System.out.println("排序前：" + java.util.Arrays.toString(arr));
// 調用冒泡排序
bubbleSort(arr);
System.out.println("排序後：" + java.util.Arrays.toString(arr));
}
}
代碼關鍵點說明¶
- 外層循環：控制排序輪數，共需
arr.length - 1輪（最後一個元素無需比較）。 - 內層循環：每輪比較相鄰元素，次數爲
arr.length - 1 - i（i爲已排好序的元素個數）。 - 交換邏輯：使用臨時變量
temp交換相鄰元素，確保排序穩定。 - 優化技巧：通過
swapped標記，若某輪無交換，提前終止排序（適用於接近有序的數組）。
時間與空間複雜度¶
- 時間複雜度：
- 最壞情況（完全逆序）：
O(n²)（需完整執行所有輪次）。 - 平均情況：
O(n²)。 - 最好情況（已排序）：
O(n)（優化後通過swapped標記提前終止）。 - 空間複雜度：
O(1)（僅需臨時變量，原地排序）。
總結¶
冒泡排序原理簡單直觀，適合初學者理解排序核心思想。但由於時間複雜度較高（O(n²)），實際應用中較少用於大規模數據，通常用於教學或小規模數據排序場景。掌握後可進一步學習更高效的排序算法（如快速排序、歸併排序等）。