Go实现常见排序算法

package main
import (
    "fmt"
)
func main() {
    arr := []int{3, 2, 4, 2, 1, 5, 6, 7, 5, 6, 7, 8, 5, 4, 3, 8, 9, 7, 6, 7}
    //快排
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}
/**
经典快排
以数组最后一位数为基准，小于的放左边 等于的放中间 大于的放右边
递归  以上  左边的  和  右边的
不稳定 最坏 O(N^2)  最好和平均 O(NlogN)
随机快排  最坏最好和平均 O(NlogN)
不取最后一位而是随机一位做基准，其他不变 所以它结合概率  期望复杂度是 O(NlogN)
*/
func quickSort(arr []int, L, R int) {
    //L不能小于R
    if L < R {
        //将数组分为左中右三部分，返回等于的区间
        partition := partition(arr, L, R)
        //递归左部分
        quickSort(arr, L, partition[0]-1)
        //递归右部分
        quickSort(arr, partition[1]+1, R)
    }
}
func partition(arr []int, L, R int) []int {
    //less下标之前的都是小于待比较数的 默认数组最小下标-1
    less := L - 1
    //more下标之后的都是大于待比较数的 默认数组最大下标+1
    more := R + 1
    //待比较数
    compare_num := arr[R] //默认为最后一位 随机快排  这个取个随机数即可
    //当前比较下标， 比较到哪个位置了
    cur := L
    for cur < more {
        //fmt.Printf("cur:%v,less:%v,more:%v", cur, less, more)
        if arr[cur] < compare_num {
            //如果当前数小于比较数，则less的后一位与当前元素交换位置并把less加1，当前cur后移一位
            arr[less+1], arr[cur] = arr[cur], arr[less+1]
            less++
            cur++
        } else if arr[cur] > compare_num {
            //如果当前数大于比较数，则more的前一位与当前元素互换位置并把more减1，此时cur不移动继续比较
            arr[more-1], arr[cur] = arr[cur], arr[more-1]
            more--
        } else {
            //相等的话直接往后面移动
            cur++
        }
        //fmt.Println(arr)
    }
    //返回 相等的区间 也就是less+1和more-1都是与比较数相等的
    return []int{less + 1, more - 1}
}

package main
import (
    "fmt"
)
func main() {
    //冒泡
    arr1 := []int{3, 2, 4, 2, 1, 5, 6, 7, 5, 6, 7, 8, 5, 4, 3, 8, 9, 7, 6, 7}
    maopaoSort(arr1)
    fmt.Println(arr1)
}
/**
冒泡 和 选择排序
复杂度最高的排序 基本不用 只做演示和教学
复杂度为 选择排序最差最好平均都是O(N^2)  冒泡最好可能是O(N)
冒泡  22比较   
选择  1和后面的全部比较
*/
func maopaoSort(arr []int) {
    //不解释了， 两两比较
    for i := 0; i < len(arr); i++ {
        for j := 0; j < len(arr)-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

package main
import (
    "fmt"
)
func main() {
    arr2 := []int{3, 2, 4, 2, 1, 5, 6, 7, 5, 6, 7, 8, 5, 4, 3, 8, 9, 7, 6, 7}
    xuanzeSort(arr2)
    fmt.Println(arr2)
}
func xuanzeSort(arr []int) {
    //不解释了， 与后面的一一比较
    for i := 0; i < len(arr); i++ {
        tmp := arr[i]
        for j := i + 1; j < len(arr); j++ {
            if tmp > arr[j] {
                tmp, arr[j] = arr[j], tmp
            }
        }
        arr[i] = tmp
    }
}

package main
import (
    "fmt"
)
func main() {
    //插入
    arr3 := []int{3, 2, 4, 2, 1, 5, 6, 7, 5, 6, 7, 8, 5, 4, 3, 8, 9, 7, 6, 7}
    charuSort(arr3)
    fmt.Println(arr3)
}
/**
插入排序
最坏平均 O(N^2)  最好 O(N)
像斗地主那样， 左边部分都是有序的， 右边拿一个按顺序插入左边
*/
func charuSort(arr []int) {
    //从1开始，默认有1个有序
    for i := 1; i < len(arr); i++ {
        //比较下一个位置，往前面有序数组中插入
        for j := i - 1; j >= 0; j-- {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

package main
import (
    "fmt"
)
func main() {
    //归并
    arr4 := []int{3, 2, 4, 2, 1, 5, 6, 7, 5, 6, 7, 8, 5, 4, 3, 8, 9, 7, 6, 7}
    arr4 = guibingSort(arr4)
    fmt.Println(arr4)
}
/**
归并排序
最坏最好平均 O(NlogN)
递归
左右 两个数组 依次比较   递归出来的左右两个数组是分别有序
*/
func guibingSort(arr []int) []int {
    //数组个数小于2直接返回
    if len(arr) < 2 {
        return arr
    }
    index := len(arr) / 2
    //归并左边的使其有序
    left := guibingSort(arr[0:index])
    //归并右边的使其有序
    right := guibingSort(arr[index:])
    //合并两个有序数组
    return merge(left, right)
}
func merge(left []int, right []int) []int {
    //临时数组
    tmp := make([]int, 0)
    //左右两个有序数组都从下标0开始比较
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            //如果左边小于右边，左边加入临时数组，左边下标+1继续比较
            tmp = append(tmp, left[i])
            i++
        } else {
            //如果左边大于右边，则相反
            tmp = append(tmp, right[j])
            j++
        }
    }
    //上面比较完可能有一方还有数组没放进去，则直接放进临时数组，下面两个语句只有一个会执行，可以让左边或右边剩下元素直接放到临时后面即可
    tmp = append(tmp, left[i:]...)
    tmp = append(tmp, right[j:]...)
    //返回合并好的有序数组
    return tmp
}

package main
import (
    "fmt"
)
func main() {
    //堆排序
    arr5 := []int{3, 2, 4, 2, 1, 5, 6, 7, 5, 6, 7, 8, 5, 4, 3, 8, 9, 7, 6, 7}
    heapSort(arr5)
    fmt.Println(arr5)
}
/**
  堆排序
  最坏最好平均 O(NlogN)
  每个数组都能转化为堆 堆其实就是一种完全二叉树，分为大根堆和小跟堆
  1>先把数组转化为大根堆
  2>一次缩小堆长度，将大根堆顶弹出，堆尾换到堆顶进行微调 直至堆长度为0
  3 4 5 4 7 9 3
        9
      5   7
    3  4 4 3
 */
func heapSort(arr []int) {
    //先把数组转化为大根堆
    for i := 0; i < len(arr); i++ {
        //（i-1)/2是父节点 如果比这个大 就交换
        for i > 0 && arr[i] > arr[(i-1)/2] {
            arr[i], arr[(i-1)/2] = arr[(i-1)/2], arr[i]
            i = (i - 1) / 2
        }
    }
    //此时arr已经转化为大根堆 开始首尾交换 [9 8 7 8 7 5 4 7 7 6 6 3 5 4 3 2 5 2 6 1]
    heapSize := len(arr)
    for heapSize > 0 {
        //首尾交换
        arr[0], arr[heapSize-1] = arr[heapSize-1], arr[0]
        //堆长度-1
        heapSize--
        //调整堆为大根堆 自上而下 子节点是 i\*2+1
        //还有子节点
        curent := 0
        for curent*2+1 < heapSize {
            large := 0
            //两个子节点比较出最大的 避免越界
            if curent*2+2 < heapSize && arr[curent*2+1] < arr[curent*2+2] {
                large = curent*2 + 2
            } else {
                large = curent*2 + 1
            }
            //比较父子节点，让小数下沉
            if arr[large] < arr[curent] {
                large = curent
            }
            //看看比较出的large是不是当前节点，如果是的话说明已经最大就跳出，不是就交换位置继续下沉
            if curent != large {
                arr[curent], arr[large] = arr[large], arr[curent]
                curent = large
            } else {
                //如果父节点已经最大了就退出
                break
            }
        }
    }
}