常用的排序算法

总结

基于比较的排序(从小到大排序)

冒泡排序

GO实现
func MySort( arr []int ) []int {
    // 冒泡
    // 大的往后冒
    for i := 0; i < len(arr); i++{
        for j := 0; j < len(arr) - 1 - i; j++ {
            if arr[j] > arr[j + 1]{
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            }
        }
    }
    return arr
}
另一种实现
func MySort( arr []int ) []int {
    // 小的往前冒
    for i := 0; i < len(arr); i++{
        for j := len(arr) - 1; j > i ; j-- {
            if arr[j] < arr[j - 1]{
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            }
        }
    }
    return arr
}

选择排序

GO实现
func MySort( arr []int ) []int {
    // 选择排序
    // 不稳定:5 5 1
    for i := 0; i < len(arr); i++{
        minPoi := i
        for j := i + 1; j < len(arr); j++{
            if arr[minPoi] > arr[j] {
                minPoi = j
            }
        }
        arr[i], arr[minPoi] = arr[minPoi], arr[i]
    }
}

直接插入排序

GO实现
func MySort( arr []int ) []int {
    // 稳定:2 2 1
    for i := 1; i < len(arr); i++ {
        if arr[i] < arr[i - 1]{
            temp := arr[i]
            j := i - 1
            for j >= 0 && temp < arr[j] {
                arr[j + 1] = arr[j]
                j--
            }
            arr[j + 1] = temp
        }
    }
}

希尔排序(第一个突破n^2的排序算法)

GO实现
func MySort( arr []int ) []int {
    // 不稳定:相同元素不在同一组,则无法保证相对顺序
    var shell func(int, int)
    shell = func(begin, step int) {
        for i := begin + step; i < len(arr); i += step {
            if arr[i] < arr[i - step] {
                temp := arr[i]
                j := i - step
                for j >= begin && temp < arr[j] {
                    arr[j + step] = arr[j]
                    j -= step
                }
                arr[j + step] = temp
            }
        }
    }
    step := len(arr)/2
    for step > 0 {
        for i := 0; i < step; i++{
            shell(i, step)
        }
        step /= 2
    }
}

归并排序

GO实现
func MySort( arr []int ) []int {
    // 2 2 1 稳定
    if len(arr) < 2 {
        return arr
    }
    mid := len(arr)/2
    left := arr[:mid]
    right := arr[mid:]
    var merge func([]int, []int) []int
    merge = func(left []int, right []int)(ans []int){
        i := 0
        j := 0
        for i < len(left) && j < len(right){
            if left[i] <= right[j] {
                ans = append(ans, left[i])
                i++
            }else{
                ans = append(ans, right[j])
                j++
            }
        }
        ans = append(ans, left[i:]...)
        ans = append(ans, right[j:]...)
        return
    }
    return merge(MySort(left), MySort(right))
}

快速排序

GO实现
func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    // 2,2,1 不稳定
    var quicSort func(int, int)
    quicSort = func(begin, end int) {
        if(end - begin <= 0){
            return
        }
        cur := arr[begin]
        left := begin
        right := end
        isRight := true
        for left != right {
            if isRight {
                if arr[right] < cur {
                    arr[left] = arr[right]
                    isRight = !isRight
                }else{
                    right--
                }
            } else {
                if arr[left] > cur {
                    arr[right] = arr[left]
                    isRight = !isRight
                }else{
                    left++
                }
            }
        }
        arr[left] = cur
        quicSort(begin, left - 1)
        quicSort(left + 1, end)
    }
    quicSort(0, len(arr) - 1)
}

堆排序

有两种建堆方式:从顶向下O(n)(已知堆的大小),从底向上O(nlogn)(堆的大小动态调整)
参考博文:【堆/排序】堆排序的两种建堆方法

GO实现
func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    // 不稳定 2 2 1
    // 从小到大排序,用大顶堆,每次把根节点放最后,然后end - 1
    var down func(int, int) 
    down = func(start int, end int){
        for start < end {
            fmt.Println(start)
            left := 2 * start + 1
            right := 2 * start + 2
            if left > end {
                break
            }
            max := arr[left]
            if right <= end && arr[right] > max{
                max = arr[right]
            }
            if max > arr[start] {
                if max == arr[left] {
                    arr[start], arr[left] = arr[left], arr[start]
                    start = left
                } else {
                    arr[start], arr[right] = arr[right], arr[start]
                    start = right
                }
            }else{
                break
            }
        }
    }
    end := len(arr) - 1
    // 先建堆
    // end的父节点是:(end - 1)/2
    for i := (end - 1)/2; i >= 0; i-- {
        down(i, end)
    }
    fmt.Println(arr[end])
    // 再排序
    for end >= 1 {
        arr[0], arr[end] = arr[end], arr[0]
        end--
        down(0, end)
    }
}

非比较排序(基于桶排序思想)

计数排序(适合数据跨度小,重复数据多的情况)

相当于为每个数字安排一个桶

GO实现
func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    minArr := math.MaxInt
    maxArr := -1
    for _, v := range arr {
        if minArr > v {
            minArr = v
        }
        if maxArr < v {
            maxArr = v
        }
    }
    record := make([]int, maxArr - minArr + 1)
    for _, v := range arr {
        record[v - minArr]++
    }
    cur := 0
    for i, v := range record {
        for v > 0 {
            arr[cur] = i + minArr
            cur++
            v--
        }
    }
}

基数排序(桶排序的变种)

一位一位的来处理数据,桶的数量固定为十个,桶间有序,桶内无序。
有两种处理方式:

  • 从最高位到最低位:每个桶内要再进行桶排序
  • 从最低位到最高位:只要调用最大数的最高位数次排序就行
GO实现
func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    // 找到最大值
    maxValue := -1
    for _, v := range arr {
        if maxValue < v {
            maxValue = v
        }
    }
    // 找到最高位
    maxBit := 0
    for maxValue != 0 {
        maxValue /= 10
        maxBit++
    }
    // fmt.Println(maxBit)
    // 声明十个桶
    buckets := make([][]int, 10)
    base := 1
    for i := 0; i < maxBit; i++ {
        for _, v := range arr {
            buckets[(v / base) % 10] = append(buckets[(v/base)%10], v)
        }
        index := 0
        for j, bucket := range buckets {
            if len(bucket) == 0 {
                // fmt.Println(len(bucket))
                continue
            }
            for _, v := range bucket{
                arr[index] = v
                index++
            }
            // 清空桶
            buckets[j] = buckets[j][:0]
        }
        base *= 10
    }
    return arr
}
tips

是不是很疑惑我为什么没写桶排序?

  • 要使用桶排序算法,首先要确定桶的数量,这一点就很麻烦
  • 由于桶内是无序的,所以往往还需要在桶内调用快排之类的基于比较的排序算法,所以我个人觉得桶排序不能算非比较排序,所以没有写

热门相关:冉冉心动   利用私贷赚钱的老婆   大妆   后福   买妻种田:山野夫君,强势宠!