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

冒泡排序相关复杂度：

选择排序

选择排序也很容易理解，对于一个无序的数组，我们每次都从数组中寻找最小值，并把它和第一个元素交换。

如下图，有测试数据 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

Leetcode 的排序相关题目会在排序专题结束之后进行推荐。