10-交換排序：冒泡排序-有解無憂

一：冒泡排序的思想

（1）冒泡排序是交換排序的一種，另一種交換排序是快速排序；

（2）冒泡排序演算法的基本思想是：假設待排序表長為n,從后往前(從右往左)（或從前往后（從左往右））兩兩比較相鄰元素的值，若為逆序（即arr[j-1]>arr[j]）,則交換它們，直到序列比較完，這稱之為一趟冒泡排序，結果是將最小的元素交換到待排序序列的第一個位置（最小的元素如氣泡一般逐漸往上“漂浮”直至“水面”，這就是冒泡排序名字的由來），下一趟冒泡時，前一趟確定的最小元素不再參與比較，待排序序列減少一個元素，每趟冒泡的結果把序列中的最小元素放到了序列的最終位置上，...，這樣最多經過n-1趟冒泡就能把所有的元素排好序；

（3）冒泡排序的偽代碼如下所示（王道資料結構版本）：

 1 void bubbleSort(ElemType A[],int n){
 2     // 用冒泡排序法將序列A中的元素按從小到大排列
 3     for(int=0;i<n-1;i++){
 4         flag = false;                         // 表示本趟冒泡是否發生交換的標志
 5         for(j=n-1;j>i;j--){                   // 一趟冒泡的程序
 6             if(A[j-1].key > A[j].key){        // 若為逆序
 7                 swap(A[j-1],A[j]);            // 交換
 8                 flag = true;
 9             }
10         }
11         if(falg = false){
12             break;                            // 本趟遍歷后沒有發生交換，說明表已經有序，直接跳出回圈
13         }
14     }
15 }

（4）冒泡排序性能總結：

　　（4.1）空間效率：空間復雜度為O(1);

　　 (4.2) 時間效率：最好時間復雜度O(n), 最壞時間復雜度O(n²), 平均時間復雜度O(n²)；

　　 (4.3) 穩定性：是穩定的排序方法，

（5）常見代碼實作

（5.1）從小到大排序，從左往右比較(從前往后比較),不考慮性能優化問題

 1 package cn.sun.it.thread;
 2 
 3 import java.util.Arrays;
 4 import java.util.Scanner;
 5 
 6 public class BubbleSort_V1 {
 7 
 8     public static void main(String[] args) {
 9         // 10 1 35 61 89 36 55
10         // 9,8,7,6,5,4,3,2,1
11         Scanner sc = new Scanner(System.in);
12         System.out.println("請輸入若干個整數，以逗號分隔：");
13         String strNumbers = sc.nextLine();
14         String[] tempNums = strNumbers.split(",");
15         int[] arr = new int[tempNums.length];
16         for (int i = 0; i < arr.length; i++) {
17             arr[i] = Integer.valueOf(tempNums[i]);
18         }
19         System.out.println("->排序前：" + Arrays.toString(arr));
20         bubbleSort_v1(arr);
21         System.out.println("->排序后：" + Arrays.toString(arr));
22 
23     }
24     
25     // 從小到大排序，從左往右比較(從前往后比較),不考慮性能優化問題
26         public static void bubbleSort_v1(int[] arr){
27             for(int i=0;i<arr.length-1;i++){
28                 for(int j=0;j<arr.length-1-i;j++){
29                     if(arr[j]>arr[j+1]){
30                         int temp = arr[j];
31                         arr[j] = arr[j+1];
32                         arr[j+1] = temp;
33                     }
34                     System.out.println("第"+(i+1)+"趟，第"+(j+1)+"次排序結果為："+Arrays.toString(arr));
35                 }
36                 System.out.println("*第"+(i+1)+"趟排序結果為："+Arrays.toString(arr));
37             }
38         }
39 
40 }

輸出結果:

（5.2）從小到大排序，從右往左比較(從后往前比較),不考慮性能優化問題

 1 package cn.sun.it.thread;
 2 
 3 import java.util.Arrays;
 4 import java.util.Scanner;
 5 
 6 public class BubbleSort_V2 {
 7 
 8     public static void main(String[] args) {
 9         // 10 1 35 61 89 36 55
10         // 7,6,5,4,3,2,1
11         Scanner sc = new Scanner(System.in);
12         System.out.println("請輸入若干個整數，以逗號分隔：");
13         String strNumbers = sc.nextLine();
14         String[] tempNums = strNumbers.split(",");
15         int[] arr = new int[tempNums.length];
16         for (int i = 0; i < arr.length; i++) {
17             arr[i] = Integer.valueOf(tempNums[i]);
18         }
19         System.out.println("->排序前：" + Arrays.toString(arr));
20         bubbleSort_v2(arr);
21         System.out.println("->排序后：" + Arrays.toString(arr));
22 
23     }
24 
25     // 從小到大排序，從右往左比較(從后往前比較),不考慮性能優化問題
26     public static void bubbleSort_v2(int[] arr) {
27         for (int i = 0; i < arr.length - 1; i++) {
28             int count = 0;
29             for (int j = arr.length - 1; j > i; j--) {
30                 if (arr[j] < arr[j - 1]) {
31                     int temp = arr[j - 1];
32                     arr[j - 1] = arr[j];
33                     arr[j] = temp;
34 
35                 }
36                 System.out.println("第" + (i + 1) + "趟，第" + (++count) + "次排序結果為：" + Arrays.toString(arr));
37             }
38             System.out.println("*第" + (i + 1) + "趟排序結果為：" + Arrays.toString(arr));
39         }
40     }
41 
42 }

輸出結果：

（5.3）從小到大排序，從左往右比較(從前往后比較),考慮性能優化問題

 1 package cn.sun.it.thread;
 2 
 3 import java.util.Arrays;
 4 import java.util.Scanner;
 5 
 6 public class BubbleSort_V3 {
 7 
 8     public static void main(String[] args) {
 9         // 10,1,35,61,89,36,55
10         // 7,6,5,4,3,2,1
11         Scanner sc = new Scanner(System.in);
12         System.out.println("請輸入若干個整數，以逗號分隔：");
13         String strNumbers = sc.nextLine();
14         String[] tempNums = strNumbers.split(",");
15         int[] arr = new int[tempNums.length];
16         for (int i = 0; i < arr.length; i++) {
17             arr[i] = Integer.valueOf(tempNums[i]);
18         }
19         System.out.println("->排序前：" + Arrays.toString(arr));
20         bubbleSort_v3(arr);
21         System.out.println("->排序后：" + Arrays.toString(arr));
22 
23     }
24 
25     // 從小到大排序，從左往右比較(從前往后比較),考慮性能優化問題
26     public static void bubbleSort_v3(int[] arr) {
27         int temp = 0;
28         boolean flag = false;
29         for (int i = 0; i < arr.length - 1; i++) {
30             for (int j = 0; j < arr.length - 1 - i; j++) {
31                 if (arr[j] > arr[j + 1]) {
32                     temp = arr[j];
33                     arr[j] = arr[j + 1];
34                     arr[j + 1] = temp;
35                     flag = true;
36                 }
37                 System.out.println("第" + (i + 1) + "趟，第" + (j + 1) + "次排序結果為：" + Arrays.toString(arr));
38             }
39             System.out.println("第" + (i + 1) + "趟排序結果為：" + Arrays.toString(arr));
40             if (!flag) {
41                 break;
42             } else {
43                 flag = false;
44             }
45         }
46     }
47 }

輸出結果：

（5.4）從小到大排序，從右往左比較(從后往前比較),考慮性能優化問題

 1 package cn.sun.it.thread;
 2 
 3 import java.util.Arrays;
 4 import java.util.Scanner;
 5 
 6 public class BubbleSort_V4 {
 7 
 8     public static void main(String[] args) {
 9         // 10,1,35,61,89,36,55
10         // 7,6,5,4,3,2,1
11         Scanner sc = new Scanner(System.in);
12         System.out.println("請輸入若干個整數，以逗號分隔：");
13         String strNumbers = sc.nextLine();
14         String[] tempNums = strNumbers.split(",");
15         int[] arr = new int[tempNums.length];
16         for (int i = 0; i < arr.length; i++) {
17             arr[i] = Integer.valueOf(tempNums[i]);
18         }
19         System.out.println("->排序前：" + Arrays.toString(arr));
20         bubbleSort_v4(arr);
21         System.out.println("->排序后：" + Arrays.toString(arr));
22 
23     }
24 
25     // 從小到大排序，從右往左比較(從后往前比較),考慮性能優化問題
26     public static void bubbleSort_v4(int[] arr) {
27         int temp = 0;
28         boolean flag = false;
29         for (int i = 0; i < arr.length - 1; i++) {
30             int count = 0;
31             for (int j = arr.length - 1; j > i; j--) {
32                 if (arr[j] < arr[j - 1]) {
33                     temp = arr[j];
34                     arr[j] = arr[j - 1];
35                     arr[j - 1] = temp;
36                     flag = true;
37                 }
38                 System.out.println("第" + (i + 1) + "趟，第" + (++count) + "次排序結果為：" + Arrays.toString(arr));
39             }
40             System.out.println("第" + (i + 1) + "趟排序結果為：" + Arrays.toString(arr));
41             if (!flag) {
42                 break;
43             } else {
44                 flag = false;
45             }
46         }
47     }
48 }

輸出結果：

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/270769.html

標籤：其他

上一篇：蟻群演算法解決任務調度問題-Python

下一篇：資料結構亂扯