冒泡排序（Bubble Sort）

1. 冒泡排序：是一種簡單的排序算法，其基本思想是通過重復遍歷要排序的列表，比較相鄰的元素，并在必要時（即前面的數比后面的數大的時候）交換它們的位置，從而將較大的元素逐漸“冒泡”到列表的末尾。這個過程會重復進行（第一次把最大的元素放在列表的末尾，第二次把第二大的元素放在列表的倒數第二的位置，以此類推，只需執行(數組的長度-1次)這個過程即可），直到整個列表被排序。
   • 冒泡排序主要有兩個for循環組成
     • 外層for循環主要用于控制數組循環遍歷的次數
       • 數組的長度決定要遍歷的次數
     • 內層for循環主要用于元素位置的交換（把較大的元素往后移動）

冒泡排序初代代碼：減少比較次數

• 優化點：每經過一輪冒泡，內層循環就可以減少一次

public class BubbleSort {public static void main(String[] args) {int[] arr ={24,69,80,57,13};System.out.println("排序前的數組:");printArray(arr);bubbleSort(arr);System.out.println("排序后的數組:");printArray(arr);}/*** 冒泡排序算法* @param arr：數組*/public static void bubbleSort(int[] arr) {int n = arr.length; // 數組長度// 外層循環是控制數組循環遍歷的次數：默認要循環【數組的長度-1】遍，每遍歷一次子循環的比較次數就減少一次（因為每次子循環會把最大的一個元素放在數組的最后）for (int i = 0; i < n - 1; i++) {// 內層循環控制每一次循環的比較和元素的交換（一輪冒泡）for (int j = 0; j < n - 1 - i; j++) {  // n-1-i表示要比較的元素的個數if (arr[j] > arr[j + 1]) { // 如果前一個元素大于后一個元素，則交換int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true; // 當數組元素發生交換說明數組當前不是有序的}}}}// 打印數組public static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}}

案例分析

1. 以int[] arr= {24,69,80,57,13};舉例
   • 外層for循環第1輪：把最大的數放在最后的位置
     • 前一個數和后一個數比較，如果前者大就交換位置（內層for循環）
       • 第1次比較[24,69,80,57,13] 第1個和第2個比
       • 第2次比較[24,69,80,57,13] 第2個和第3個比
       • 第3次比較[24,69,57,80,13] 第3個和第4個比（80比57大，所以80和57交換位置）
       • 第4次比較[24,69,57,13,80] 第4個和第5個比（80比13大，所以80和13交換位置）
   • 外層for循環第2輪：把第二大的數放在倒數第二個位置
     • 前一個數和后一個數比較，如果前者大就交換位置（內層for循環）
       • 第1次比較[24,69,57,13,80] 第1個和第2個比
       • 第2次比較[24,57,69,13,80] 第2個和第3個比
       • 第3次比較[24,57,13,69,80] 第3個和第4個比
   • 外層for循環第3輪：把第三大的數放在倒數第三個位置
     • 前一個數和后一個數比較，如果前者大就交換位置（內層for循環）
       • 第1次比較[24,57,13,69,80] 第1個和第2個比
       • 第2次比較[24,13,57,69,80] 第2個和第3個比
   • 外層for循環第4輪：把第四大的數放在倒數第四個位置
     • 前一個數和后一個數比較，如果前者大就交換位置（內層for循環）
       • 第1次比較[13,24,57,69,80] 第1個和第2個比

• 總結
  • 1. 一共有5個元素（數組的長度為n，n=5）
  • 2. 一共進行了4輪排序（需要進行n-1輪排序）
  • 3. 每一輪排序可以確定一個數的位置，比如第一輪排序確定最大的數…
  • 4. 當進行比較時，如果前面的數大于后面的數，就交換
  • 5. 每輪的比較次數在減少4->3->2->1

冒泡排序改進代碼：通過swapped變量減少冒泡次數

• 優化點：如果某一輪冒泡沒有發生交換，則表示所有數據有序，可以結束外層循環

public class BubbleSort {public static void main(String[] args) {int[] arr ={24,69,80,57,13};System.out.println("排序前的數組:");printArray(arr);bubbleSort(arr);System.out.println("排序后的數組:");printArray(arr);}/*** 冒泡排序算法* @param arr：數組*/public static void bubbleSort(int[] arr) {int n = arr.length; // 數組長度boolean swapped;// 外層循環是控制數組循環遍歷的次數：默認要循環【數組的長度-1】遍，每遍歷一次子循環的比較次數就減少一次（因為每次子循環會把最大的一個元素放在數組的最后）for (int i = 0; i < n - 1; i++) {swapped = false;  // 判斷數組是否有序，false表示有序（默認）// 內層循環控制每一次循環的比較和元素的交換（一輪冒泡）for (int j = 0; j < n - 1 - i; j++) {  // n-1-i表示要比較的元素的個數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 printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}}

冒泡排序最終實現

• 優化點：用一個死循環作為外層循環，每次通過記錄最后一次交換索引位置進行判斷，如果在索引為0的位置，則可以結束循環。

public class BubbleSort {public static void main(String[] args) {int[] arr ={24,69,80,57,13};System.out.println("排序前的數組:");printArray(arr);bubbleSort(arr);System.out.println("排序后的數組:");printArray(arr);}/*** 冒泡排序算法* @param arr：數組*/public static void bubbleSort(int[] arr) {int n = a.length - 1;while (true) {int last = 0; // 表示最后一次交換索引位置for (int i = 0; i < n; i++) {System.out.println("比較次數" + i);if (a[i] > a[i + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;last = i;}}n = last;System.out.println("第輪冒泡"+ Arrays.toString(a));if (n == 0) { // 表示最后一次交換索引位置break;}}}// 打印數組public static void printArray(int[] arr) {for (int num : arr) {System.out.print(num + " ");}System.out.println();}}

• 一直冒泡，每輪冒泡時，最后一次交換的索引可以作為下一輪冒泡的比較次數，如果這個值為零，表示整個數組有序，直接退出外層循環即可。