泡沫排序法，用golang實作

定義

過程中，會將兩個數字兩兩比較，將比較大的直接換到較後面的位置，就像氣泡一樣，慢慢的從底部浮現出來，因此取名氣泡排序法。

流程如下

比較相鄰兩個元素，將兩個相鄰的元素較大的放後面，較小的放前面
重複第一個動作，直到沒有元素需要比較為止

特性

穩定的排序方式 => 相同鍵值的元素，排序之後相對位置不改變
原地排序＝> 不需花費額外的空間來儲存排序結果

時間複雜度

最佳時間(Best Case) : O(n) => 資料剛好順序由小到大
最差狀態(Worst Case): O(n^2) =>順序剛好由大到小，每一個都需要排序的時候
- 每回合執行: n-1, n-2 …..1 次 => (n-1)+ (n-2) ＋…..＋ 1 = n(n-1)/2 => O(n^2)
平均時間(Average Case) :O(n^2) => 第 N 筆資料，平均比較(n-1)/2 次

範例

[1,43,6,79,50,2]

第一次疊代

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// 依照順序，與位置做比較
// 檢查 1跟 43 (第一個位置，與第二個位置)=> 不需要交換
[1,43,6,79,50,2]
 * *
// 檢查 43 跟 6  (第二個位置，與第三個位置），因為 43 比 6 大，要交換！
[1,43,6,79,50,2]  => [1,6,43,79,50,2] 
   *  *                 * *
// 檢查 43 跟 79  (第三個位置，與第四個位置）=> 不需要交換
 [1,6,43,79,50,2]
      *  *
// 檢查 79 跟 50  (第四個位置，與第五個位置），因為 79 比 43 大，要交換！
[1,6,43,79,50,2]  => [1,6,43,50,79,2]
        *  *                 *  *
// 檢查 79 跟 50  (第五個位置，與第六個位置），因為 79 比 2 大，要交換！
[1,6,43,50,79,2]  => [1,6,43,50,2,79]
           *  *                 *  *

這樣最大的已經被換到最後面去了

第二次疊代

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// 依照順序，與位置做比較
// 檢查 1跟 6 (第一個位置，與第二個位置)=> 不需要交換
[1,6,43,50,2,79]
 * *
// 檢查 6 跟 43  (第二個位置，與第三個位置）=> 不需要交換
[1,6,43,50,2,79]  => [1,6,43,50,2,79]
   * *                  * *
// 檢查 43 跟 50  (第三個位置，與第四個位置）=> 不需要交換
[1,6,43,50,2,79]
     *  *
// 檢查 50 跟 2  (第四個位置，與第五個位置），因為 50 比 2 大，要交換！
[1,6,43,50,2,79]  => [1,6,43,2,50,79]
        *  *                 * *
--- 以下迴圈還是會跑，但後面最大的都排序，故不會動 ---
// 檢查 50 跟 79  (第五個位置，與第六個位置)=> 不需要交換
 [1,6,43,2,50,79] 
           *  *   

第三次疊代

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// 依照順序，與位置做比較
// 檢查 1跟 6 (第一個位置，與第二個位置)=> 不需要交換
[1,6,43,2,50,79]
 * *

// 檢查 6 跟 43  (第二個位置，與第三個位置）=> 不需要交換
[1,6,43,2,50,79]  => [1,6,43,2,50,79]
   * *                  * *

// 檢查 43 跟 2  (第三個位置，與第四個位置）=> ，因為 43 比 2 大，要交換！
[1,6,43,2,50,79] => [1,6,2,43,50,79]
     *  *                * *

--- 以下迴圈還是會跑，但後面最大的都排序，故不會動 ---
// 檢查 43 跟 50  (第四個位置，與第五個位置）=> 不需要交換
[1,6,2,43,50,79]
        *  *     
// 檢查 50 跟 79  (第五個位置，與第六個位置)=> 不需要交換
[1,6,2,43,50,79]
          *  *  

第四次疊代

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// 依照順序，與位置做比較
// 檢查 1跟 6 (第一個位置，與第二個位置)=> 不需要交換
[1,6,2,43,50,79]
 * *

// 檢查 6 跟 2 (第二個位置，與第三個位置）=> ，因為 6 比 2 大，要交換！
[1,6,2,43,50,79]  => [1,2,6,43,50,79]
   * *                  * *

--- 以下迴圈還是會跑，但後面最大的都排序，故不會動 ---

// 檢查 43 跟 2  (第三個位置，與第四個位置）=> 不需要交換
[1,2,6,43,50,79]
     *  * 
// 檢查 43 跟 50  (第四個位置，與第五個位置）=> 不需要交換
[1,2,6,43,50,79]
        *  *     
// 檢查 50 跟 79  (第五個位置，與第六個位置)=> 不需要交換
[1,2,6,43,50,79]
          *  *  

第五次疊代

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


// 檢查 1跟 2 (第一個位置，與第二個位置)=> 不需要交換
[1,2,6,43,50,79]
 * *

--- 以下迴圈還是會跑，但後面最大的都排序，故不會動 ---
// 檢查 6 跟 2 (第二個位置，與第三個位置）=> 不需要交換
[1,2,6,43,50,79]
   * * 
// 檢查 43 跟 2  (第三個位置，與第四個位置）=> 不需要交換
[1,2,6,43,50,79]
     *  * 
// 檢查 43 跟 50  (第四個位置，與第五個位置）=> 不需要交換
[1,2,6,43,50,79]
        *  *     
// 檢查 50 跟 79  (第五個位置，與第六個位置)=> 不需要交換
[1,2,6,43,50,79]
          *  * 

就排序完成了

實作 Golang

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func BubbleSort(input []int){
	// 泡沫排序法
	inputLen := len(input)
	stopFlag := true
	for stopFlag{
		stopFlag = false
		for item := 0; item < inputLen-1; item++ {
			if input[item] > input[item+1] {
				input[item], input[item+1] = input[item+1],input[item]
				stopFlag = true
			}
		}
	}
}