[[404642]]

本文轉載自微信公眾號「roseduan寫字的地方」，作者roseduan。轉載本文請聯系roseduan寫字的地方公眾號。

錄制 rosedb 視頻的時候，挖了個坑，說要用 Go 語言實現常見的數據結構和算法，雖然現在這樣的文章已經很多了，但是玫瑰哥??有坑必填!只能硬著頭皮寫了，這個系列，就叫做 Go 語言算法之美吧!

排序是一個十分古老的問題，也是計算機領域很經典的算法問題之一，后續的幾篇文章，我將對常見的排序算法進行講述。

我將會附上完整的代碼，并且推薦一些相關的 Leetcode 題目，不僅可以用來學習鞏固算法知識，還能夠幫助你在面試當中，更加的游刃有余。

本篇文章介紹三種基礎排序算法：冒泡排序、選擇排序、插入排序。

冒泡排序

冒泡排序基于比較并交換，基本思路是遍歷數據，如果相鄰的元素大小不等，則交換它們的位置，如此循環往復，直到數據完全有序。

如下圖，有測試數據 -2 45 0 11 -9。

在第一次遍歷當中，會將數據中最大值 45 移動至末尾，然后在除了 45 的數據內再次遍歷，將最大值移動至 45 之前。這樣遍歷完最后一個元素，數據即是有序的了。

下圖比較直觀的展示了冒泡排序的流程：

代碼如下：

func bubbleSort(data []int) { 
   for i := 0; i < len(data); i++ { 
      for j := 0; j < len(data)-i-1; j++ { 
         if data[j] > data[j+1] { 
            data[j], data[j+1] = data[j+1], data[j] 
         } 
      } 
   } 
} 

這里有一個小的優化點，如果數據本來就是有序的，例如 1 3 4 5 6 ，遍歷一次之后，會發現沒有任何數據進行交換，可以提前退出，不用繼續進行遍歷了，代碼上可以進行優化，如下：

func bubbleSort(data []int) { 
   swap := true 
   for i := 0; i < len(data) && swap; i++ { 
      swap = false 
      for j := 0; j < len(data)-i-1; j++ { 
         if data[j] > data[j+1] { 
            data[j], data[j+1] = data[j+1], data[j] 
            swap = true 
         } 
      } 
   } 
} 

冒泡排序相關復雜度：

選擇排序

選擇排序也很容易理解，對于一個無序的數組，我們每次都從數組中尋找最小值，并把它和第一個元素交換。

如下圖，有測試數據 20 12 10 15 2，第一次遍歷，尋找到最小值是 2：

并將其與數組的第一個元素進行交換：

然后在剩下的數據中繼續尋找最小值，然后將其與數組第二個元素交換，如此循環往復，直到最后一個數據，這樣整個數組便是有序的了。

下面這張動圖可以幫助你理解選擇排序的整個過程：

代碼實現：

func selectionSort(data []int) { 
   for i := 0; i < len(data)-1; i++ { 
      min := i 
      for j := i + 1; j < len(data); j++ { 
         if data[j] < data[min] { 
            min = j 
         } 
      } 
      data[i], data[min] = data[min], data[i] 
   } 
} 

選擇排序相關復雜度：

插入排序

回想一下我們在玩紙牌游戲時，是如何將手中的紙牌變得有順序的?當新來了一張紙牌，我們會在手中已有的紙牌中查找到合適的位置，將其插入。

插入排序也是這樣的，依次遍歷數組中的每一個數據，將其插入到合適的位置，下面的這張動圖比較形象的說明了這個過程：

代碼實現如下：

func insertionSort(data []int) { 
   for i := 0; i < len(data)-1; i++ { 
      j, k := i+1, data[i+1] 
      for ; j > 0 && data[j-1] > k; j-- { 
         data[j] = data[j-1] 
      } 
      data[j] = k 
   } 
} 

插入排序相關復雜度：

備注：完整代碼我放到了我的 Github 上面，地址：

https://github.com/roseduan/Go-Algorithm