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 str[j] {str[j-1], str[j] = str[j], str[j-1]}}}// 反向冒泡for i := 0; i 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 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 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 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 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)}//堆调整函数0func 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] { //父节点大于孩子节点break}str[index] = str[j] //给节点赋值index = j //index此时已代表孩子节点下标}str[index] = temp //给孩子节点赋值，到此代表节点的值跟孩子节点中的较大值进行互换完成}//堆调整函数1func Heap_Adjust_1(str []int, length, index int) {parent := indexchild := parent*2 + 1for ; child <= length-1; child *= 2 {if child str[child] {child++}if str[child] > str[parent] {str[child], str[parent] = str[parent], str[child]parent = child}}}//堆调整函数2func Heap_Adjust_2(str []int, length, index int) {largest := index // 初始化最大元素为根节点left := 2*index + 1 // 左子节点索引right := 2*index + 2 // 右子节点索引// 如果左子节点大于根节点if left str[largest] {largest = left}// 如果右子节点大于最大元素if 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 = 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 = 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(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(left) {result[k] = right[j]j++} else if j >= len(right) {result[k] = left[i]i++} else if left[i] 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}
