了解冒泡排序演算法(附Java範例)
Bubble Sort詳解:一個簡單的排序演算法
冒泡排序是最簡單的排序演算法之一。它的工作原理是反覆比較相鄰元素,如果它們順序不對,則交換它們。例如,如果排序順序是升序,則比較相鄰元素,並將較大的元素放在右邊。每次迭代中,我們只比較未排序的元素,並將最大的元素放在數組未排序元素的最後一個位置。
演算法恰如其分地命名為冒泡排序,因為元素在每次迭代中都會向數組的右側移動,就像水泡上升到水面一樣。
冒泡排序的工作原理
假設我們要以升序排列這個陣列:
第一次迭代
在第一次迭代中,我們嘗試將最大元素移到陣列的末端。因此,我們將重複比較相鄰元素,如果它們順序不對,則交換它們。
已移動到正確位置的元素被認為已排序。
後續迭代
這個過程對所有迭代重複進行,直到陣列排序完畢。在每次迭代中,我們只比較未排序的元素,因為已排序的元素已經按正確的順序排列。
我們迭代遍歷數組 n-1 次,其中 n 是數組的長度。也就是說,由於我們的陣列有六個元素,我們只迭代遍歷數組五次。這是因為,在第五次迭代之後,五個元素已經放置在其正確的位置,因此最終的未排序元素被認為已排序。所有迭代完成後,我們將得到一個排序後的陣列。
冒泡排序的實作
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>未排序数组: [8, 2, 6, 4, 9, 1] 已排序数组: [1, 2, 4, 6, 8, 9]</code>
在這個冒泡排序的實作中,即使數組已經排序,我們也會每次都迭代遍歷數組。我們可以進一步優化程式碼,以便一旦數組已排序就停止排序。
最佳化的冒泡排序
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; } }
透過這個實現,如果我們嘗試對一個已經排序的數組進行排序,我們將只迭代一次,並在沒有進行排序時停止。
冒泡排序的複雜度
時間複雜度:
最佳情況 (O(n)):
最佳情況是輸入陣列已經排序。演算法只迭代一次數組以檢查它是否已排序,並且不執行任何交換。
平均情況 (O(n²)):
當輸入數組元素處於隨機順序時。演算法必須進行多次迭代並執行交換以對數組進行排序。
最壞情況 (O(n²)):
最壞情況是輸入數組依反向順序排序。演算法進行 n-1 次迭代並執行最大數量的交換。
空間複雜度 O(1):
冒泡排序是一種就地排序演算法,也就是說,它不需要任何與輸入數組大小成比例的額外記憶體。
結論
冒泡排序是一種易於理解且實現的演算法。但是,由於其時間複雜度高,因此不適合用於處理大型資料集。在處理小型資料集時,或者當你不關心複雜度時,可以使用冒泡排序。
以上是了解冒泡排序演算法(附Java範例)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

公司安全軟件導致部分應用無法正常運行的排查與解決方法許多公司為了保障內部網絡安全,會部署安全軟件。 ...

系統對接中的字段映射處理在進行系統對接時,常常會遇到一個棘手的問題:如何將A系統的接口字段有效地映�...

將姓名轉換為數字以實現排序的解決方案在許多應用場景中,用戶可能需要在群組中進行排序,尤其是在一個用...

在使用MyBatis-Plus或其他ORM框架進行數據庫操作時,經常需要根據實體類的屬性名構造查詢條件。如果每次都手動...

在使用IntelliJIDEAUltimate版本啟動Spring...

Java對象與數組的轉換:深入探討強制類型轉換的風險與正確方法很多Java初學者會遇到將一個對象轉換成數組的�...

電商平台SKU和SPU表設計詳解本文將探討電商平台中SKU和SPU的數據庫設計問題,特別是如何處理用戶自定義銷售屬...

在使用TKMyBatis進行數據庫查詢時,如何優雅地獲取實體類變量名以構建查詢條件,是一個常見的難題。本文將針...
