归并排序 Go语言实现经典算法


归并排序原理

归并排序使用经典的分治法(Divide and conquer)策略。分治法会将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之。
归并排序原理图

效率

时间复杂度 O(nlogn)
空间复杂度O(n) + O(logn)
排序时间与输入无关,最佳情况,最坏情况都是如此。

稳定性

归并排序是稳定排序

归并排序的Go语言实现代码

package main

import (
    "fmt"
    "time"
    "math/rand"
)

func merge(numArr []int, L int, M int, R int){
    // 重新准备一个临时数组,用于存放要排序的数据
    temp := make([]int, R-L+1)
    for i := L; i <= R; i++ {
        temp[i-L] = numArr[i]
    }

    // 标记两部分起点
    left := 0
    right := M+1-L

    for i := L ; i <= R; i++ {
        if left+L > M {
            // 左边越过中线,说明只剩右边的数据
            numArr[i] = temp[right]
            right++
        }else if right+L > R {
            // 右边越过边界,说明只剩左边的数据
            numArr[i] = temp[left]
            left++
        }else if temp[left] < temp[right]{
            // 左小右大,取右边
            numArr[i] = temp[right]
            right++
        }else {
            // 左大右小,取左边
            numArr[i] = temp[left]
            left++
        }
    }
}

func mergeSort(numArr []int, L int, R int){
    if( L == R ){
        return
    }
    var M int
    M = (L+R)/2

    mergeSort(numArr,L,M)

    mergeSort(numArr,M+1,R)

    merge(numArr, L, M, R)
}

// 归并排序 类似于后序遍历二叉树
func main(){

    rand.Seed(time.Now().UnixNano())

    numArr := make([]int,10)
    for i := range numArr{
        numArr[i] = rand.Intn(100)
    }
    fmt.Println(numArr)
    // fmt.Println(numArr[3:9])
    mergeSort(numArr,0,len(numArr)-1)
    fmt.Println(numArr)
}

本文发表于2019年12月13日 17:59
阅读 434 讨论 0 喜欢 1

抢先体验

扫码体验
趣味小程序
文字表情生成器

闪念胶囊

又是一年五一,祝我们工人阶级劳动节快乐! 今年被困在北京了,离境再入境需要隔离十五天。只能京津冀周边走一走了,想出去玩啊啊啊啊啊~

人活一辈子,不是一年两年。时间是有连续性的,做抉择的时候要多看几步。保持警惕,大丈夫有所为,有所不为。

跟人接触,不要想:我能从你身上得到什么,要想:我能给你什么。 想通了,内核就稳了。

这个世界上,别人只会看你现在的样子而不是以后的样子。你以后的样子只有自己才相信。如果没有执行力,一切都是虚妄。

对普通人来说,人和人相处其实最重要的是感觉。感觉不好,你说什么都没用,怎么解释都没用,越说越错,反正最后不好的锅都往你身上扣。所谓“说你行你就行,不行也行。说你不行,你就不行,行也不行”就是这个意思。狼要吃人根本不需要理由,你也同样叫不醒装睡的人。遇到这种情况,早点闪人才是上策。不过大部分人的问题是没有闪人的心态,能力,和资源。

快捷链接
网站地图
提交友链
Copyright © 2016 - 2020 Cion.
All Rights Reserved.
ICP备案:鲁ICP备19012333号-4.

鲁公网安备 37061302000383号.