package mainimport "fmt"func main() {Bubble_Sort()Select_Sort()Insert_Sort()Shell_Sort()Heap_Sort()Merge_Sort()Quick_Sort()
}

一、

1、冒泡排序?

// 冒泡排序
func Bubble_Sort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}// 正向冒泡for i := 0; i < len(str)-1; i++ {for j := 1; j <= len(str)-1; j++ {if str[j-1] > str[j] {str[j-1], str[j] = str[j], str[j-1]}}}// 反向冒泡for i := 0; i < len(str)-1; i++ {for j := len(str) - 1; j > i; j-- {if str[j-1] > str[j] {str[j-1], str[j] = str[j], str[j-1]}}}//改進for i := 0; i < len(str)-1; i++ {flag := falsefor j := 1; j <= len(str)-1; j++ {if str[j-1] > str[j] {str[j-1], str[j] = str[j], str[j-1]flag = true}}if !flag {break}}fmt.Println(str)
}

2、快速排序

func Quick_Sort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}Quicking_Sort(str, 0, 8)fmt.Println(str)
}
func Quicking_Sort(str []int, low, high int) {if low < high {pivot := Partition_1(str, low, high)Quicking_Sort(str, low, pivot-1)Quicking_Sort(str, pivot+1, high)}
}func Partition_0(str []int, low, high int) int {//選取基準點。也可以從三個數或者九個數中選取大小為中間值的數作為基準pivotkey := str[low]for low < high { //從表的兩端交替向中間掃描for low < high && str[high] > pivotkey {high--}//1、交換法//str[low], str[high] = str[high], str[low]for low < high && str[low] < pivotkey {low++}//1、交換法//str[low], str[high] = str[high], str[low]//2、統一交換str[low], str[high] = str[high], str[low]}return low
}func Partition_1(str []int, low, high int) int {//選取基準點。也可以從三個數或者九個數中選取大小為中間值的數作為基準pivotkey := str[low]temp := pivotkeyfor low < high { //從表的兩端交替向中間掃描for low < high && str[high] > pivotkey {high--}//替換法str[low] = str[high]for low < high && str[low] < pivotkey {low++}//替換法str[high] = str[low]}str[low] = tempreturn low
}func Partition_2(str []int, low, high int) int {pivotkey := str[high] // 選擇最后一個元素作為基準值i := lowfor j := low; j < high; j++ {// 將比 pivot 小的數丟到 [l...i-1] 中，剩下的 [i...j] 區間都是比 pivot 大的if str[j] < pivotkey {// 互換 i、j 下標對應數據str[i], str[j] = str[j], str[i]// 將 i 下標后移一位i++}}// 最后將 pivot 與 i 下標對應數據值互換// 這樣一來，pivot 就位于當前數據序列中間，i 也就是 pivot 值對應的下標str[i], str[high] = pivotkey, str[i]// 返回 i 作為 pivot 分區位置return i
}

二、

1、選擇排序?

// 選擇排序
func Select_Sort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}for i := 0; i < len(str)-1; i++ {// 未排序區間最小值初始化為第一個元素min := i// 從未排序區間第二個元素開始遍歷，直到找到最小值for j := i + 1; j <= len(str)-1; j++ {if str[min] > str[j] {min = j}}// 將最小值與未排序區間第一個元素互換位置（等價于放到已排序區間最后一個位置）if min != i {str[min], str[i] = str[i], str[min]}}fmt.Println(str)
}

2、堆排序??

//堆排序
func Heap_Sort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}//構建一個大頂堆for i := len(str) / 2; i > 0; i-- {Heap_Adjust_2(str, len(str), i)}for i := len(str) - 1; i > 0; i-- {str[0], str[i] = str[i], str[0]Heap_Adjust_2(str, i, 0) //將剩余的重新調整為大頂堆}fmt.Println(str)
}//堆調整函數0
func Heap_Adjust_0(str []int, length, index int) {temp := str[index]for j := 2*index + 1; j <= length-1; j *= 2 { //沿關鍵字較大的孩子節點向下篩選if j < length-1 && str[j] < str[j+1] {j++ //j記錄孩子節點較大的下標}if temp > str[j] { //父節點大于孩子節點break}str[index] = str[j] //給節點賦值index = j           //index此時已代表孩子節點下標}str[index] = temp //給孩子節點賦值，到此代表節點的值跟孩子節點中的較大值進行互換完成}//堆調整函數1
func Heap_Adjust_1(str []int, length, index int) {parent := indexchild := parent*2 + 1for ; child <= length-1; child *= 2 {if child < length-1 && str[child+1] > str[child] {child++}if str[child] > str[parent] {str[child], str[parent] = str[parent], str[child]parent = child}}
}//堆調整函數2
func Heap_Adjust_2(str []int, length, index int) {largest := index     // 初始化最大元素為根節點left := 2*index + 1  // 左子節點索引right := 2*index + 2 // 右子節點索引// 如果左子節點大于根節點if left < length && str[left] > str[largest] {largest = left}// 如果右子節點大于最大元素if right < length && str[right] > str[largest] {largest = right}// 如果最大元素不是根節點if largest != index {str[index], str[largest] = str[largest], str[index]// 遞歸調整受影響的子樹Heap_Adjust_2(str, length, largest)}
}

三、

1、插入排序

//插入排序
func Insert_Sort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}for i := 1; i <= len(str)-1; i++ {temp := str[i]j := i - 1for ; j >= 0 && str[j] > temp; j-- {str[j+1] = str[j]}str[j+1] = temp}fmt.Println(str)
}

2、希爾排序

//希爾排序   與插入排序比較，把原來按順序變成了相隔增量
func Shell_Sort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}//increment相隔數量// for increment := len(str) / 3; increment > 0; increment /= 3 {increment := len(str)for increment > 0 {increment = increment / 3//此過程類似于插入排序的過程for i := increment; i <= len(str)-1; i++ {key := str[i]j := i - increment//按照increment，數組從j到0進行交換比較for ; j >= 0 && str[j] > key; j -= increment {str[j+increment] = str[j]}//如果是從for循環走到這里，此時j<0，因為for循環走完時j-=increment ，所以要加回來//走到這里時，j已經減掉increment 了，所以要加回來str[j+increment] = key}}fmt.Println(str)
}

四、歸并排序?

// 歸并排序
func Merge_Sort() {str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}str = Merging_Sort(str)fmt.Println(str)
}
func Merging_Sort(str []int) []int {// str := []int{9, 1, 5, 8, 3, 7, 4, 6, 2}if len(str) <= 1 {return str}mid := len(str) / 2 //獲取分區位置//進行遞歸分區left := Merging_Sort(str[:mid])right := Merging_Sort(str[mid:])res := Merge_0(left, right) //函數將兩個有序數組合并成一個有序數組return res
}func Merge_0(left, right []int) []int {// 用于存放結果集result := make([]int, len(left)+len(right))i, j, k := 0, 0, 0for ; k < len(result); k++ {// 任何一個區間遍歷完，則退出if i >= len(left) || j >= len(right) {break}// 對所有區間數據進行排序if left[i] < right[j] {result[k] = left[i]i++} else {result[k] = right[j]j++}}// 如果左側區間還沒有遍歷完，將剩余數據放到結果集if i <= len(left) {for l := 0; l < len(left)-i; l++ {result[k+l] = left[i+l]}}// 如果右側區間還沒有遍歷完，將剩余數據放到結果集if j <= len(right) {for l := 0; l < len(right)-j; l++ {result[k+l] = right[j+l]}}return result
}func Merge_1(left, right []int) []int {result := make([]int, len(left)+len(right))i, j := 0, 0for k := 0; k < len(result); k++ {if i >= len(left) {result[k] = right[j]j++} else if j >= len(right) {result[k] = left[i]i++} else if left[i] < right[j] {result[k] = left[i]i++} else {result[k] = right[j]j++}}return result
}func Merge_2(left, right []int) []int {// result := make([]int, len(left)+len(right))//此處不能用make初始化[]int切片，//因為make初始化后，result=[]int{0,0,0},再用append，result=[]int{0,0,0,5},//相當于直接在result后面添加數據，會導致結果多了很多0var result []intfor len(left) > 0 || len(right) > 0 {if len(left) == 0 {return append(result, right...)}if len(right) == 0 {return append(result, left...)}if left[0] < right[0] {result = append(result, left[0])left = left[1:]} else {result = append(result, right[0])right = right[1:]}}return result
}