[TOC] ## 算法介紹 時間復雜度都是：`O(n^2)` 現在有一堆亂序的數，比如：`5 9 1 6 8 14 6 49 25 4 6 3`。 第一輪迭代：從第一個數開始，**依次比較相鄰的兩個數**，如果前面一個數比后面一個數大，那么交換位置，直到處理到最后一個數，最后的這個數是最大的。 第二輪迭代：因為最后一個數已經是最大了，現在重復第一輪迭代的操作，但是只處理到倒數第二個數。 第三輪迭代：因為最后一個數已經是最大了，最后第二個數是次大的，現在重復第一輪迭代的操作，但是只處理到倒數第三個數。 第N輪迭代：.... ``` []表示排好序 {}表示比較后交換的結果 第一輪開始： 4 2 9 1 從第一個數開始，4 比 2 大，交換 4，2 第一輪： {2 4} 9 1 接著 4 比 9 小，不交換 第一輪： 2 {4 9} 1 接著 9 比 1 大，交換 9，1 第一輪： 2 4 {1 9} 已經到底，結束 第一輪結果： 2 4 1 [9] 第二輪開始：2 4 1 [9] 從第一個數開始，2 比 4 小，不交換 第二輪： {2 4} 1 [9] 接著 4 比 1 大，交換 4，1 第二輪： 2 {1 4} [9] 已經到底，結束 第二輪結果： 2 1 [4 9] 第三輪開始：2 1 [4 9] 從第一個數開始，2 比 1 大，交換 2，1 第三輪： (1 2} [4 9] 已經到底，結束 第三輪結果： 1 [2 4 9] 結果： [1 2 4 9] ``` ## 實例 <details> <summary>描述</summary> ``` package main import "fmt" func BubbleSort(list []int) { n := len(list) // 在一輪中有沒有交換過 didSwap := false // 進行 N-1 輪迭代 for i := n - 1; i > 0; i-- { // 每次從第一位開始比較，比較到第 i 位就不比較了，因為前一輪該位已經有序了 for j := 0; j < i; j++ { // 如果前面的數比后面的大，那么交換 if list[j] > list[j+1] { list[j], list[j+1] = list[j+1], list[j] didSwap = true } } // 如果在一輪中沒有交換過，那么已經排好序了，直接返回 if !didSwap { return } } } func main() { list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3} BubbleSort(list) fmt.Println(list) //[1 3 4 5 6 6 6 8 9 14 25 49] } ``` </details> <br/> 冒泡排序是效率較低的排序算法，可以說是最慢的排序算法了，我們只需知道它是什么，在實際工作上切勿使用如此之慢的排序算法!