本文转载自微信公众号「roseduan写字的地方」，作者roseduan。转载本文请联系roseduan写字的地方公众号。

录制 rosedb 视频的时候，挖了个坑，说要用 Go 语言实现常见的数据结构和算法，虽然现在这样的文章已经很多了，但是玫瑰哥??有坑必填!只能硬着头皮写了，这个系列，就叫做 Go 语言算法之美吧!

排序是一个十分古老的问题，也是计算机领域很经典的算法问题之一，后续的几篇文章，我将对常见的排序算法进行讲述。

我将会附上完整的代码，并且推荐一些相关的 Leetcode 题目，不仅可以用来学习巩固算法知识，还能够帮助你在面试当中，更加的游刃有余。

本篇文章介绍三种基础排序算法：冒泡排序、选择排序、插入排序。

冒泡排序

冒泡排序基于比较并交换，基本思路是遍历数据，如果相邻的元素大小不等，则交换它们的位置，如此循环往复，直到数据完全有序。

如下图，有测试数据 -2 45 0 11 -9。

在第一次遍历当中，会将数据中最大值 45 移动至末尾，然后在除了 45 的数据内再次遍历，将最大值移动至 45 之前。这样遍历完最后一个元素，数据即是有序的了。

下图比较直观的展示了冒泡排序的流程：

代码如下：

funcbubbleSort(data[]int){
fori:=0;i<len(data);i++{
forj:=0;j<len(data)-i-1;j++{
ifdata[j]>data[j+1]{
data[j],data[j+1]=data[j+1],data[j]
}
}
}
}

这里有一个小的优化点，如果数据本来就是有序的，例如 1 3 4 5 6 ，遍历一次之后，会发现没有任何数据进行交换，可以提前退出，不用继续进行遍历了，代码上可以进行优化，如下：

funcbubbleSort(data[]int){
swap:=true
fori:=0;i<len(data)&&swap;i++{
swap=false
forj:=0;j<len(data)-i-1;j++{
ifdata[j]>data[j+1]{
data[j],data[j+1]=data[j+1],data[j]
swap=true
}
}
}
}

冒泡排序相关复杂度：

选择排序

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

如下图，有测试数据 20 12 10 15 2，第一次遍历，寻找到最小值是 2：

并将其与数组的第一个元素进行交换：

然后在剩下的数据中继续寻找最小值，然后将其与数组第二个元素交换，如此循环往复，直到最后一个数据，这样整个数组便是有序的了。

下面这张动图可以帮助你理解选择排序的整个过程：

代码实现：

funcselectionSort(data[]int){
fori:=0;i<len(data)-1;i++{
min:=i
forj:=i+1;j<len(data);j++{
ifdata[j]<data[min]{
min=j
}
}
data[i],data[min]=data[min],data[i]
}
}

选择排序相关复杂度：

插入排序

回想一下我们在玩纸牌游戏时，是如何将手中的纸牌变得有顺序的?当新来了一张纸牌，我们会在手中已有的纸牌中查找到合适的位置，将其插入。

插入排序也是这样的，依次遍历数组中的每一个数据，将其插入到合适的位置，下面的这张动图比较形象的说明了这个过程：

代码实现如下：

funcinsertionSort(data[]int){
fori:=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