Bubble Sort詳解：一個簡單的排序演算法
冒泡排序是最簡單的排序演算法之一。它的工作原理是反覆比較相鄰元素，如果它們順序不對，則交換它們。例如，如果排序順序是升序，則比較相鄰元素，並將較大的元素放在右邊。每次迭代中，我們只比較未排序的元素，並將最大的元素放在數組未排序元素的最後一個位置。
演算法恰如其分地命名為冒泡排序，因為元素在每次迭代中都會向數組的右側移動，就像水泡上升到水面一樣。
假設我們要以升序排列這個陣列：
在第一次迭代中，我們嘗試將最大元素移到陣列的末端。因此，我們將重複比較相鄰元素，如果它們順序不對，則交換它們。
已移動到正確位置的元素被認為已排序。
這個過程對所有迭代重複進行，直到陣列排序完畢。在每次迭代中，我們只比較未排序的元素，因為已排序的元素已經按正確的順序排列。
我們迭代遍歷數組 n-1 次，其中 n 是數組的長度。也就是說，由於我們的陣列有六個元素，我們只迭代遍歷數組五次。這是因為，在第五次迭代之後，五個元素已經放置在其正確的位置，因此最終的未排序元素被認為已排序。所有迭代完成後，我們將得到一個排序後的陣列。
<code class="language-java">public class BubbleSortTest {
public static void main(String[] args) {
int[] arr = {8, 2, 6, 4, 9, 1};
System.out.println("未排序数组: " + Arrays.toString(arr));
bubbleSort(arr);
System.out.println("已排序数组: " + Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
int size = arr.length;
// 循环遍历数组 size-1 次
for (int i = 0; i < size - 1; i++) {
// 比较相邻元素
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}</code>執行此程式碼將在控制台中列印以下輸出：
<code>未排序数组: [8, 2, 6, 4, 9, 1] 已排序数组: [1, 2, 4, 6, 8, 9]</code>
在這個冒泡排序的實作中，即使數組已經排序，我們也會每次都迭代遍歷數組。我們可以進一步優化程式碼，以便一旦數組已排序就停止排序。
<code class="language-java">public static void bubbleSortOptimised(int[] arr){
int size = arr.length;
boolean swapped;
// 循环遍历数组 size-1 次
for (int i = 0; i < size - 1; i++) {
swapped = false;
// 比较相邻元素
for (int j = 0; j < size - 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;
}
}</code>透過這個實現，如果我們嘗試對一個已經排序的數組進行排序，我們將只迭代一次，並在沒有進行排序時停止。
最佳情況是輸入陣列已經排序。演算法只迭代一次數組以檢查它是否已排序，並且不執行任何交換。
當輸入數組元素處於隨機順序時。演算法必須進行多次迭代並執行交換以對數組進行排序。
最壞情況是輸入數組依反向順序排序。演算法進行 n-1 次迭代並執行最大數量的交換。
冒泡排序是一種就地排序演算法，也就是說，它不需要任何與輸入數組大小成比例的額外記憶體。
冒泡排序是一種易於理解且實現的演算法。但是，由於其時間複雜度高，因此不適合用於處理大型資料集。在處理小型資料集時，或者當你不關心複雜度時，可以使用冒泡排序。
以上是了解冒泡排序演算法（附Java範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
