[[404642]]

本文轉(zhuǎn)載自微信公眾號「roseduan寫字的地方」，作者roseduan。轉(zhuǎn)載本文請聯(lián)系roseduan寫字的地方公眾號。

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

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

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

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

冒泡排序

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

如下圖，有測試數(shù)據(jù) -2 45 0 11 -9。

在第一次遍歷當(dāng)中，會將數(shù)據(jù)中最大值 45 移動至末尾，然后在除了 45 的數(shù)據(jù)內(nèi)再次遍歷，將最大值移動至 45 之前。這樣遍歷完最后一個元素，數(shù)據(jù)即是有序的了。

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

代碼如下：

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] 
         } 
      } 
   } 
} 

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

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 
         } 
      } 
   } 
} 

冒泡排序相關(guān)復(fù)雜度：

選擇排序

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

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

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

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

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

代碼實現(xiàn)：

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] 
   } 
} 

選擇排序相關(guān)復(fù)雜度：

插入排序

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

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

代碼實現(xiàn)如下：

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 
   } 
} 

插入排序相關(guān)復(fù)雜度：

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

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