雖然看過別人寫了很多遍，而且自己也寫過很多遍（指的是筆記），但是還是要寫的就是排序算法。畢竟是初學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
}