Go 语言算法之美—基础排序
本文转载自微信公众号「roseduan写字的算法地方」，作者roseduan。基础转载本文请联系roseduan写字的排序地方公众号。
录制 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 } } } }冒泡排序相关复杂度：
时间复杂度 最坏 O(n2) 最好 O(n) 平均 O(n2) 空间复杂度O(1) 是否稳定是选择排序
选择排序也很容易理解，对于一个无序的数组，我们每次都从数组中寻找最小值，并把它和第一个元素交换。
如下图，有测试数据 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] } }选择排序相关复杂度：
时间复杂度 最坏 O(n2) 最好 O(n2) 平均 O(n2) 空间复杂度O(1) 是否稳定否插入排序
回想一下我们在玩纸牌游戏时，是如何将手中的纸牌变得有顺序的?当新来了一张纸牌，我们会在手中已有的纸牌中查找到合适的位置，将其插入。香港云服务器
插入排序也是这样的，依次遍历数组中的每一个数据，将其插入到合适的位置，下面的这张动图比较形象的说明了这个过程：
代码实现如下：
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 } }插入排序相关复杂度：
时间复杂度 最坏 O(n2) 最好 O(n) 平均 O(n2) 空间复杂度O(1) 是否稳定是备注：完整代码我放到了我的 Github 上面，地址：
https://github.com/roseduan/Go-Algorithm