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
}