Go 語言算法之美—基礎排序

前言：錄製 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
         }
      }
   }
}

冒泡排序相關複雜度：

joQSxM

選擇排序

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

如下圖，有測試數據 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]
   }
}

選擇排序相關複雜度：

b0Y5to

插入排序

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

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

代碼實現如下：

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

插入排序相關複雜度：

fXDnzq

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

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/yNkxvOcqstgDWTAmuP8utw