歡迎光臨
每天分享高質量文章

排序演算法總結(1):冒泡排序

(點擊上方公號,快速關註我們)


來源:靜默虛空  
www.cnblogs.com/jingmoxukong/p/4302718.html

要點

冒泡排序是一種交換排序

什麼是交換排序呢?

交換排序:兩兩比較待排序的關鍵字,並交換不滿足次序要求的那對數,直到整個表都滿足次序要求為止。

演算法思想

它重覆地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重覆地進行直到沒有再需要交換,也就是說該數列已經排序完成。

這個演算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端,故名。

假設有一個大小為 N 的無序序列。冒泡排序就是要每趟排序過程中通過兩兩比較,找到第 i 個小(大)的元素,將其往上排。

圖-冒泡排序示例圖

以上圖為例,演示一下冒泡排序的實際流程:

假設有一個無序序列  { 4. 3. 1. 2, 5 }

第一趟排序:通過兩兩比較,找到第一小的數值 1 ,將其放在序列的第一位。

第二趟排序:通過兩兩比較,找到第二小的數值 2 ,將其放在序列的第二位。

第三趟排序:通過兩兩比較,找到第三小的數值 3 ,將其放在序列的第三位。

至此,所有元素已經有序,排序結束。

要將以上流程轉化為代碼,我們需要像機器一樣去思考,不然編譯器可看不懂。

假設要對一個大小為 N 的無序序列進行升序排序(即從小到大)。

(1) 每趟排序過程中需要通過比較找到第 i 個小的元素。

所以,我們需要一個外部迴圈,從陣列首端(下標 0) 開始,一直掃描到倒數第二個元素(即下標 N – 2) ,剩下最後一個元素,必然為最大。

(2) 假設是第 i 趟排序,可知,前 i-1 個元素已經有序。現在要找第 i 個元素,只需從陣列末端開始,掃描到第 i 個元素,將它們兩兩比較即可。

所以,需要一個內部迴圈,從陣列末端開始(下標 N – 1),掃描到 (下標 i + 1)。

核心代碼

public void bubbleSort(int[] list) {
    int temp = 0// 用來交換的臨時數

    // 要遍歷的次數
    for (int i = 0; i list
.length - 1; i++) {
        // 從後向前依次的比較相鄰兩個數的大小,遍歷一次後,把陣列中第i小的數放在第i個位置上
        for (int j = list.length - 1; j > i; j--) {
            // 比較相鄰的元素,如果前面的數大於後面的數,則交換
            if (list[j - 1] > list[j]) {
                temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }
        }

        System.out.format("第 %d 趟: ", i);
        printAll(list);
    }
}

演算法分析

冒泡排序演算法的性能

時間複雜度

若檔案的初始狀態是正序的,一趟掃描即可完成排序。所需的關鍵字比較次數C和記錄移動次數M均達到最小值:Cmin = N – 1, Mmin = 0。所以,冒泡排序最好時間複雜度為O(N)。

若初始檔案是反序的,需要進行 N -1 趟排序。每趟排序要進行 N – i 次關鍵字的比較(1 ≤ i ≤ N – 1),且每次比較都必須移動記錄三次來達到交換記錄位置。在這種情況下,比較和移動次數均達到最大值:

Cmax = N(N-1)/2 = O(N2)
Mmax = 3N(N-1)/2 = O(N2)
冒泡排序的最壞時間複雜度為O(N2)。
因此,冒泡排序的平均時間複雜度為O(N2)。

總結起來,其實就是一句話:當資料越接近正序時,冒泡排序性能越好。

演算法穩定性

冒泡排序就是把小的元素往前調或者把大的元素往後調。比較是相鄰的兩個元素比較,交換也發生在這兩個元素之間。

所以相同元素的前後順序並沒有改變,所以冒泡排序是一種穩定排序演算法。

優化

對冒泡排序常見的改進方法是加入標誌性變數exchange,用於標誌某一趟排序過程中是否有資料交換。

如果進行某一趟排序時並沒有進行資料交換,則說明所有資料已經有序,可立即結束排序,避免不必要的比較過程。

核心代碼

// 對 bubbleSort 的優化演算法
public void bubbleSort_2(int[] list) {
    int temp = 0// 用來交換的臨時數
    boolean bChange = false// 交換標誌

    // 要遍歷的次數
    for (int i = 0; i list
.length - 1; i++) {
        bChange = false;
        // 從後向前依次的比較相鄰兩個數的大小,遍歷一次後,把陣列中第i小的數放在第i個位置上
        for (int j = list.length - 1; j > i; j--) {
            // 比較相鄰的元素,如果前面的數大於後面的數,則交換
            if (list[j - 1] > list[j]) {
                temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
                bChange = true;
            }
        }

        // 如果標誌為false,說明本輪遍歷沒有交換,已經是有序數列,可以結束排序
        if (false == bChange)
            break;

        System.out.format("第 %d 趟: ", i);
        printAll(list);
    }
}
完整參考代碼

JAVA版本

代碼實現

 1 package notes.javase.algorithm.sort;
 2  
 3 import java.util.Random;
 4  
 5 public class BubbleSort {
 6  
 7     public void bubbleSort(int[] list) {
 8         int temp = 0// 用來交換的臨時數
 9  
10         // 要遍歷的次數
11         for (int i = 0; i list
.length - 1; i++) {
12             // 從後向前依次的比較相鄰兩個數的大小,遍歷一次後,把陣列中第i小的數放在第i個位置上
13             for (int j = list.length - 1; j > i; j--) {
14                 // 比較相鄰的元素,如果前面的數大於後面的數,則交換
15                 if (list[j - 1] > list[j]) {
16                     temp = list[j - 1];
17                     list[j - 1] = list[j];
18                     list[j] = temp;
19                 }
20             }
21  
22             System.out.format("第 %d 趟: ", i);
23             printAll(list);
24         }
25     }
26  
27     // 對 bubbleSort 的優化演算法
28     public void bubbleSort_2(int[] list) {
29         int temp = 0// 用來交換的臨時數
30         boolean bChange = false// 交換標誌
31  
32         // 要遍歷的次數
33         for (int i = 0; i list.length - 1; i++) {
34             bChange = false;
35             // 從後向前依次的比較相鄰兩個數的大小,遍歷一次後,把陣列中第i小的數放在第i個位置上
36             for (int j = list.length - 1; j > i; j--) {
37                 // 比較相鄰的元素,如果前面的數大於後面的數,則交換
38                 if (list[j - 1] > list[j]) {
39                     temp = list[j - 1];
40                     list[j - 1] = list[j];
41                     list[j] = temp;
42                     bChange = true;
43                 }
44             }
45  
46             // 如果標誌為false,說明本輪遍歷沒有交換,已經是有序數列,可以結束排序
47             if (false == bChange)
48                 break;
49  
50             System.out.format("第 %d 趟: ", i);
51             printAll(list);
52         }
53     }
54  
55     // 打印完整序列
56     public void printAll(int[] list) {
57         for (int value : list) {
58             System.out.print(value + " ");
59         }
60         System.out.println();
61     }
62  
63     public static void main(String[] args) {
64         // 初始化一個隨機序列
65         final int MAX_SIZE = 10;
66         int[] array = new int[MAX_SIZE];
67         Random random = new Random();
68         for (int i = 0; i 69             array[i] = random.nextInt(MAX_SIZE);
70         }
71  
72         // 呼叫冒泡排序方法
73         BubbleSort bubble = new BubbleSort();
74         System.out.print("排序前: ");
75         bubble.printAll(array);
76         // bubble.bubbleSort(array);
77         bubble.bubbleSort_2(array);
78         System.out.print("排序後: ");
79         bubble.printAll(array);
80     }
81 }

運行結果

排序前:    2    9    9    7    1    9    0    2    6    8   
第 0 趟:    0    2    9    9    7    1    9    2    6    8   
第 1 趟:    0    1    2    9    9    7    2    9    6    8   
第 2 趟:    0    1    2    2    9    9    7    6    9    8   
第 3 趟:    0    1    2    2    6    9    9    7    8    9   
第 4 趟:    0    1    2    2    6    7    9    9    8    9   
第 5 趟:    0    1    2    2    6    7    8    9    9    9   
排序後:    0    1    2    2    6    7    8    9    9    9  

【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】
《不要自稱是程式員,我十多年的 IT 職場總結》:

http://blog.jobbole.com/94148/


③ 最後請附上您的個人簡介哈~



覺得本文有幫助?請分享給更多人

關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂