虽然看过别人写了很多遍，而且自己也写过很多遍（指的是笔记），但是还是要写的就是排序算法。毕竟是初学Go语言，虽然之前写过，但是还是打算再写一遍。主要包括插入排序、选择排序、冒泡排序、快速排序、堆排序、归并排序。

先简单写下排序的思路。插入排序：每个值与前面的排序好的值比较大小，可能会交换多次；选择排序：当前值与后面的值比较大小，记录最小值的坐标，只交换一次；冒泡排序：两两比较，结果是最大的值到最后；快速排序：找分割值，小于的放小数组，大于的放大数组，再对大小数组进行快速排序；二分归并排序：这个不断二分，然后比较大小后归并返回。

---

插入排序

不断将当前坐标的值与前面的值比较，从最近的开始（因为是从小到大排序的）。时间复杂度是(1+...+n)=(1+n)n/2，也就是n的方，不过还不包括移动元素的时间，只是单纯的比较次数。

func insertSort(arr []int) []int {length := len(arr)//每个值和前面的比较for i := 1; i < length; i++{key := arr[i]j := i-1for key < arr[j] && j >= 0{   //不断让元素后移arr[j+1] = arr[j]j--}arr[j+1] = key  //将最终的位置交换}return arr
}

选择排序

选择当前坐标及后面的值中最小值的下标，并与当前坐标的值替换。并不稳定，因为当前坐标值会大幅度的跳跃，不过和插入排序都是O(1)的空间复杂度，意味着是原地排序。

func selectSort(arr []int) []int {length := len(arr)//当前值和后面比较出最小的for i :=0; i < length-1; i++{minID := ifor j := i+1; j < length; j++{if (arr[minID] > arr[j]){minID = j}arr[i], arr[minID] = arr[minID], arr[i]}}return arr
}

冒泡排序

注意一般来说使用for是因为确定范围，而这下面的第一层for循环是因为次数，每次for语句都能够确定一个元素的位置。两两比较，结果就是最大的放在了最后面。

func bubbleSort(arr []int) []int{//思路是两两比较for i := 0; i < len(arr)-1; i++{  //因为只需要确定len(arr)-1个元素的位置，最后一个元素的位置就确定了flag := 0for j := 0; j < len(arr)-i-1; j++{if arr[j] > arr[j+1]{arr[j], arr[j+1] = arr[j+1], arr[j]flag = 1} }if flag == 0{return arr}} return arr
}

快速排序

实际上就是通过比较和某一值的大小，大的放该值的右边，小的该值的放左边。利用了直接递归，不过如果比较值选的不好，时间复杂度会退化成O(n的方)，也就是每次只排好一个值的位置。

func quickSort(arr []int) []int{if len(arr) <= 1{return arr}//选值比较key := arr[0]left := []int{}right := []int{}for i := 1; i < len(arr); i++{if key > arr[i]{left = append(left,arr[i])}else{right = append(right,arr[i])}}left = quickSort(left)right = quickSort(right)return append(append(left,key),right...)
}

堆排序

这个并不好写，堆本质上是一种特殊的完全二叉树，大根堆是每个节点的值 ≥ 其子节点的值，根节点最大。小根堆则是每个节点的值 ≤ 其子节点的值，根节点最小，通常可以通过数组来实现，并且父子关系通过下标来计算。

func heapSort(arr []int) {n := len(arr)// 1. 构建大顶堆（从最后一个非叶子节点开始）for i := n/2 - 1; i >= 0; i-- {heapify(arr, n, i)}// 2. 逐个提取堆顶元素（最大值）到数组末尾for i := n - 1; i > 0; i-- {arr[0], arr[i] = arr[i], arr[0] // 交换堆顶与末尾元素heapify(arr, i, 0)              // 对剩余元素重新堆化}
}// 堆化函数：维护以 root 为根的子树满足大顶堆性质
func heapify(arr []int, n, root int) {largest := root     // 初始化最大值为根节点left := 2*root + 1  // 左子节点right := 2*root + 2 // 右子节点// 找出根、左、右中的最大值if left < n && arr[left] > arr[largest] {largest = left}if right < n && arr[right] > arr[largest] {largest = right}// 若最大值不是根节点，则交换并递归调整if largest != root {arr[root], arr[largest] = arr[largest], arr[root]heapify(arr, n, largest)}
}

归并排序

递归深度可以算是logn，每次merge合并是n，时间复杂度估计是O(nlogn)。不过空间复杂度是O(n)，这和递归没有关系，想象一棵递归树，所有叶节点的合并操作​​总空间需求为 O(n)​​（各层空间不叠加）。

func mergeSort(arr []int) []int{//先二分length := len(arr)if length <= 1 {return arr}mid := length/2left := mergeSort(arr[:mid])right := mergeSort(arr[mid:])return merge(left,right)
}
func merge(left []int, right []int) []int{//核心原理是不断将小值放到前面lenght := len(left) + len(right)slice := make([]int,0,lenght)i,j := 0,0for i < len(left) && j < len(right){if left[i] < right[j]{slice = append(slice,left[i])i++}else{slice = append(slice,right[j])j++}}slice = append(slice, left[i:]...)slice = append(slice, right[j:]...)return slice
}