[[404642]]

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

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

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

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

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

冒泡排序

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

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

在第一次遍歷當(dāng)中，會(huì)將數(shù)據(jù)中最大值 45 移動(dòng)至末尾，然后在除了 45 的數(shù)據(jù)內(nèi)再次遍歷，將最大值移動(dòng)至 45 之前。這樣遍歷完最后一個(gè)元素，數(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] 
         } 
      } 
   } 
} 

這里有一個(gè)小的優(yōu)化點(diǎn)，如果數(shù)據(jù)本來(lái)就是有序的，例如 1 3 4 5 6 ，遍歷一次之后，會(huì)發(fā)現(xiàn)沒(méi)有任何數(shù)據(jù)進(jìn)行交換，可以提前退出，不用繼續(xù)進(jìn)行遍歷了，代碼上可以進(jìn)行優(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ù)雜度：

選擇排序

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

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

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

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

下面這張動(dòng)圖可以幫助你理解選擇排序的整個(gè)過(guò)程：

代碼實(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ù)雜度：

插入排序

回想一下我們?cè)谕婕埮朴螒驎r(shí)，是如何將手中的紙牌變得有順序的?當(dāng)新來(lái)了一張紙牌，我們會(huì)在手中已有的紙牌中查找到合適的位置，將其插入。

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

代碼實(shí)現(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