前言
排序，对于每种编程语言都是要面对的。这里跟大家一起分享golang实现一些排序算法，并且说明如何生成随机数。下面话不多说了，来一起看看详细的介绍吧。
经典排序算法
算法的学习非常重要，是检验一个程序员水平的重要标准。学习算法不能死记硬背，需要理解其中的思想，这样才能灵活应用到实际的开发中。
七大经典排序算法
插入排序 选择排序 冒泡排序 希尔排序 归并排序 堆排序 快速排序插入排序
先考虑一个问题：对于长度为n的数组，前n-1位都是递增有序的，如何排序？
1.从第1位至第n-1位遍历数组，发现第n位数字应该放在第k位
2.把第k位至第n-1位的数字依次向后挪一位
3.这样长度为n的数组就是递增有序的了
具体实现方法：
package main
import "fmt"
func insertionSort(arr []int) {
for i := 1; i < len(arr); i++ {
value := arr[i]
for j := i - 1; j >= 0; j-- {
if value < arr[j] {
arr[j+1], arr[j] = arr[j], value
} else {
break
}
}
}
}
func main() {
arr := []int{6, 5, 4, 3, 2, 1, 0}
insertionSort(arr)
fmt.Println("Sorted arr: ", arr)
}
复杂度：
时间复杂度：O(n*n）
空间复杂度：额外空间O(1)
O表达式（Big O notation）通常用来在计算机科学中表示算法的复杂度，包括：
时间复杂度：衡量算法的运行时间
空间复杂度：衡量算法运行所占的空间，比如内存或硬盘等
一般情况下，O表达式代表的是最坏情况下的复杂度。
算法分析也是如此，在n个随即数中查找某个数字，最好的情况是第一个数字就是，此时时间复杂度为O(1)，若最后一个数字才是我们要找的，那么时间复杂度是O(n)，这是最坏的情况。而平均运行时间是从概率的角度看，若数字在每一个位置都可能出现，则平均查找次数为n/2次。
平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定数量的实验数据后估算而来的。而最坏运行时间是一种保证，那就是运行时间不会再坏了。在应用中，这是最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况下的运行时间。即，时间复杂度是最坏情况下的时间复杂度。
常见的算法时间复杂度由小到大依次为：
O(1)<O(log2n)<O(n)<O(n log2 n)<O(n^2)<O(n^3)<O(2^n)
这里的O就是一般表示复杂度的一个标志，类似计算复杂度的函数名称一样。
