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

漫畫:什麼是氣泡排序?

(點選上方公眾號,可快速關註)


來源:程式員小灰



—————  當天上午  —————


什麼是氣泡排序?


氣泡排序的英文Bubble Sort,是一種最基礎的交換排序


大家一定都喝過汽水,汽水中常常有許多小小的氣泡,嘩啦嘩啦飄到上面來。這是因為組成小氣泡的二氧化碳比水要輕,所以小氣泡可以一點一點向上浮動。

而我們的氣泡排序之所以叫做氣泡排序,正是因為這種排序演演算法的每一個元素都可以像小氣泡一樣,根據自身大小,一點一點向著陣列的一側移動。


具體如何來移動呢?讓我們來看一個慄子:


有8個陣列成一個無序數列:5,8,6,3,9,2,1,7,希望從小到大排序。


按照氣泡排序的思想,我們要把相鄰的元素兩兩比較,根據大小來交換元素的位置,過程如下:


首先讓5和8比較,發現5比8要小,因此元素位置不變。


接下來讓8和6比較,發現8比6要大,所以8和6交換位置。



繼續讓8和3比較,發現8比3要大,所以8和3交換位置。



繼續讓8和9比較,發現8比9要小,所以元素位置不變。


接下來讓9和2比較,發現9比2要大,所以9和2交換位置。


接下來讓9和1比較,發現9比1要大,所以9和1交換位置。


最後讓9和7比較,發現9比7要大,所以9和7交換位置。



這樣一來,元素9作為數列的最大元素,就像是汽水裡的小氣泡一樣漂啊漂,漂到了最右側。


這時候,我們的氣泡排序的第一輪結束了。數列最右側的元素9可以認為是一個有序區域,有序區域目前只有一個元素。

下麵,讓我們來進行第二輪排序:

首先讓5和6比較,發現5比6要小,因此元素位置不變。


接下來讓6和3比較,發現6比3要大,所以6和3交換位置。


繼續讓6和8比較,發現6比8要小,因此元素位置不變。


接下來讓8和2比較,發現8比2要大,所以8和2交換位置。


接下來讓8和1比較,發現8比1要大,所以8和1交換位置。


繼續讓8和7比較,發現8比7要大,所以8和7交換位置。

第二輪排序結束後,我們數列右側的有序區有了兩個元素,順序如下:


至於後續的交換細節,我們這裡就不詳細描述了,第三輪過後的狀態如下:

第四輪過後狀態如下:

第五輪過後狀態如下:


第六輪過後狀態如下:


第七輪過後狀態如下(已經是有序了,所以沒有改變):

第八輪過後狀態如下(同樣沒有改變):

到此為止,所有元素都是有序的了,這就是氣泡排序的整體思路。


原始的氣泡排序是穩定排序。由於該排序演演算法的每一輪要遍歷所有元素,輪轉的次數和元素數量相當,所以時間複雜度是O(N^2) 


氣泡排序第一版:


public class BubbleSort {

  1. private static void sort(int array[])

  2. {

  3.    int tmp  = 0;

  4.    
       
    for(int i = 0; i < array.length; i++){

  5.        for(int j = 0; j < array.length - i - 1; j++)

  6.        {

  7.            if(array[j] > array[j+1])

  8.            {

  9.                tmp = array[j];

  10.                array[j] = array[j+1];

  11.                array[j+1] = tmp;

  12.            }

  13.        }

  14.    }

  15. }

  16. public static void main(String[] args){

  17.    int[] array = new int[]{5,8,6,3,9,2,1,7};

  18.    sort(array);

  19.    System.out.println(Arrays.toString(array));

  20. }

}

程式碼非常簡單,使用雙迴圈來進行排序。外部迴圈控制所有的回合,內部迴圈代表每一輪的冒泡處理,先進行元素比較,再進行元素交換。



————————————



原始的氣泡排序有哪些最佳化點呢?


讓我們回顧一下剛才描述的排序細節,仍然以5,8,6,3,9,2,1,7這個數列為例,當排序演演算法分別執行到第六、第七、第八輪的時候,數列狀態如下:

很明顯可以看出,自從經過第六輪排序,整個數列已然是有序的了。可是我們的排序演演算法仍然“兢兢業業”地繼續執行第七輪、第八輪。


這種情況下,如果我們能判斷出數列已經有序,並且做出標記,剩下的幾輪排序就可以不必執行,提早結束工作。


氣泡排序第二版

public class BubbleSort {

  1. private static void sort(int array[])

  2. {

  3.     int tmp  = 0;

  4.    for(int i = 0; i < array.length; i++)

  5.    {

  6.        //有序標記,每一輪的初始是true

  7.        boolean isSorted = true;

  8.        for(int j = 0; j < array.length - i - 1; j++)

  9.        {

  10.            if(array[j] > array[j+1])

  11.            {

  12.                tmp = array[j];

  13.                array[j] = array[j+1];

  14.                array[j+1] = tmp;

  15.                //有元素交換,所以不是有序,標記變為false

  16.                isSorted = false;

  17.            }

  18.        }

  19.        if(isSorted){

  20.            break;

  21.        }

  22.    }

  23. }

  24. public static void main(String[] args){

  25.    int[] array = new int[]{5,8,6,3,9,2,1,7};

  26.    sort(array);

  27.    System.out.println(Arrays.toString(array));

  28. }

}

這一版程式碼做了小小的改動,利用布林變數isSorted作為標記。如果在本輪排序中,元素有交換,則說明數列無序;如果沒有元素交換,說明數列已然有序,直接跳出大迴圈。




為了說明問題,咱們這次找一個新的數列:


這個數列的特點是前半部分(3,4,2,1)無序,後半部分(5,6,7,8)升序,並且後半部分的元素已經是數列最大值。


讓我們按照氣泡排序的思路來進行排序,看一看具體效果:


第一輪


元素3和4比較,發現3小於4,所以位置不變。


元素4和2比較,發現4大於2,所以4和2交換。

元素4和1比較,發現4大於1,所以4和1交換。


元素4和5比較,發現4小於5,所以位置不變。


元素5和6比較,發現5小於6,所以位置不變。


元素6和7比較,發現6小於7,所以位置不變。


元素7和8比較,發現7小於8,所以位置不變。


第一輪結束,數列有序區包含一個元素:


第二輪


元素3和2比較,發現3大於2,所以3和2交換。



元素3和1比較,發現3大於1,所以3和1交換。

元素3和4比較,發現3小於4,所以位置不變。


元素4和5比較,發現4小於5,所以位置不變。


元素5和6比較,發現5小於6,所以位置不變。


元素6和7比較,發現6小於7,所以位置不變。


元素7和8比較,發現7小於8,所以位置不變。

第二輪結束,數列有序區包含一個元素:

這個問題的關鍵點在哪裡呢?關鍵在於對數列有序區的界定。


按照現有的邏輯,有序區的長度和排序的輪數是相等的。比如第一輪排序過後的有序區長度是1,第二輪排序過後的有序區長度是2 ......


實際上,數列真正的有序區可能會大於這個長度,比如例子中僅僅第二輪,後面5個元素實際都已經屬於有序區。因此後面的許多次元素比較是沒有意義的。


如何避免這種情況呢?我們可以在每一輪排序的最後,記錄下最後一次元素交換的位置,那個位置也就是無序數列的邊界,再往後就是有序區了。


氣泡排序第三版


public class BubbleSort {

  1. private static void sort(int array[])

  2. {

  3.    int tmp  = 0;

  4.    //記錄最後一次交換的位置

  5.    int lastExchangeIndex = 0;

  6.    //無序數列的邊界,每次比較只需要比到這裡為止

  7.    int sortBorder = array.length - 1;

  8.    for(int i = 0; i < array.length; i++)

  9.    {

  10.        //有序標記,每一輪的初始是true

  11.        boolean isSorted = true;

  12.        for(int j = 0; j < sortBorder; j++)

  13.        {

  14.            if(array[j] > array[j+1])

  15.            {

  16.                tmp = array[j];

  17.                array[j] = array[j+1];

  18.                array[j+1] = tmp;

  19.                //有元素交換,所以不是有序,標記變為false

  20.                isSorted = false;

  21.                //把無序數列的邊界更新為最後一次交換元素的位置

  22.                lastExchangeIndex = j;

  23.            }

  24.        }

  25.        sortBorder = lastExchangeIndex;

  26.        if(isSorted){

  27.            break;

  28.        }

  29.    }

  30. }


  31. public static void main(String[] args){

  32.    int[] array = new int[]{3,4,2,1,5,6,7,8};

  33.    sort(array);

  34.    System.out.println(Arrays.toString(array));

  35. }

}

這一版程式碼中,sortBorder就是無序數列的邊界。每一輪排序過程中,sortBorder之後的元素就完全不需要比較了,肯定是有序的。



幾點補充:


本漫畫純屬娛樂,還請大家儘量珍惜當下的工作。


【關於投稿】


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


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

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

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


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


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

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

贊(0)

分享創造快樂

© 2024 知識星球   網站地圖