Go语言归并排序算法实现

算法导论的伪代码:

MERGE 函数是合并两个已经排好序的序列。

下面的输入参数:A是一个数组,p,q和r是数组下标,满足 p<=q<=r。下面的函数假设子数组 A[p…q] 和 A[q+1...r]都是已经拍好序的。这个函数将这两个子数组合并成数组A[p...r]

下面的函数MERGE-SORT排序子数组A[p...r]中的元素,如果p>=r,则该子元素最有有一个元素,所以是已经排好序的。否则,分解步骤简单的计算一个下标q,将A[p...r]分成两个子数组A[p...q]和A[q+1...r]。

Go语言的实现代码:

package main

import "fmt"

func main(){

    arr01:=[]int{34,45,3,6,76,34,46,809,92,8}

    fmt.Print("排序前")
    fmt.Println(arr01)

    mergeSort(arr01,0,len(arr01)-1)

    fmt.Print("排序后")
    fmt.Println(arr01)
}

fund merge1(arr []int,low,mid,high int){
    leftLen:=mid-low+1
    rightLen:=high-mid

    arrLeft:=make([]int,leftLen+1)
    for i:=0;i<leftLen;i++{
        arrLeft[i]=arr[low+i]
    }
    arrLeft[leftLen]=99999//哨兵牌

    arrRight:=make([]int,rightLen+1)
    forj:=0;j<rightLen;j++{
        arrRight[j]=arr[mid+j+1]
    }
    arrRight[rightLen]=99999//哨兵牌

    i,j:=0,0
    for k:=low;k<=high;k++{
        if arrLeft[i]<=arrRight[j]{
            arr[k]=arrLeft[i]
            i++
        }else{
            arr[k]=arrRight[j]
            j++
        }
    }
}

fund mergeSort(arr []int,low,high int){
    if low<high{
        mid:=(low+high)/2
        mergeSort(arr,low,mid)
        mergeSort(arr,mid+1,high)
        merge1(arr,low,mid,high)
    }
}

上面merge代码中,我们可以发现在两个辅助的最后均加入了一个较大的数,即为判断的“哨兵牌”。这样当最后进行循环操作时,每当露出一张“哨兵牌”,程序可以知道该循环已经要结束了。因为“哨兵牌”不可能是两张中较小的,除非另一个数组也出现了“哨兵牌”。如果两个数组均出现了“哨兵牌”,那么就说明了所有的元素都已经放入了数组a中了,而由于数组a的大小限制,循环已经结束了。如果没有设置“哨兵牌”,可能导致一个数组已经没有了元素,而另外一个数组还有一个元素没有放入a中,那么循环中的if判断语句就会失败,直接跳转执行else里面的语句,会导致结果出错。
如果不使用“哨兵牌”,我们同样可以实现merge所做的任务。代码如下:
主要逻辑就是一旦数据 left ,right 所有元素被复制回 arr,就立即停止循环,然后再用一个循环把另外的数组剩余部分复制过去。
可以参考:http://www.cnblogs.com/xjeternity/archive/2011/4/21.html

fund merge2(arr []int,low,mid,highint){
    leftLen:=mid-low+1
    rightLen:=high-mid

    arrLeft:=make([]int,leftLen)
    for i:=0;i<leftLen;i++{
        arrLeft[i]=arr[low+i]
    }

    arrRight:=make([]int,rightLen)
    for j:=0;j<rightLen;j++{
        arrRight[j]=arr[mid+j+1]
    }

    i,j,k:=0,0,low
    for ;k<=high&&i<leftLen&&j<rightLen;k++{
        if arrLeft[i]<=arrRight[j]{
            arr[k]=arrLeft[i]
            i++
        }else{
            arr[k]=arrRight[j]
            j++
        }
    }

    for ;i<leftLen&&k<=high;k++{
        arr[k]=arrLeft[i]
        i++
    }

    for ;j<rightLen&&k<=high;k++{
        arr[k]=arrRight[j]
        j++
    }

}

参考资料:

http://www.cnblogs.com/lxy15329/archive/2013/01/24/sort.html

http://www.cnblogs.com/tonykong/archive/2013/02/05/merge_sort.html

http://www.cnblogs.com/xjeternity/archive/2011/4/21.html

本文分享自微信公众号 - Golang语言社区(Golangweb)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-02-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xiaoheike

如何在运行时(Runtime)获得泛型的真正类型

由于Java 的类型擦除机制,在编译时泛型都被转为了Object,例如List<String>经过编译之后将变为类型 List。可以通过以下的方式再运行时获得泛...

19220
来自专栏增长技术

位运算

12420
来自专栏熊二哥

JDK1.8快速入门

JDK8提供了非常多的便捷用法和语法糖,其编码效率几乎接近于C#开发,maven则是java目前为止最赞的jar包管理和build工具,这两部分内容都不算多,就...

23190
来自专栏测试开发架构之路

C语言之位运算

指针和位运算很适合编写系统软件的需要。 位运算指进行二进制位的运算。   按位与”运算符 & 用途 1)清零 2)取一个数中某些指定位(比如只需要低8位) 3)...

611100
来自专栏desperate633

一篇文章搞懂面试中leetcode位操作算法题Single Number落单的数落单的数 IISingle Number IISingle Number III落单的数 IIINumber of 1

本文将根据题目总结常用的位操作常用的解决算法问题的技巧 如读者对基本的位操作概念还不熟悉,可以先参考笔者的文章浅谈程序设计中的位操作http://www.ji...

7710
来自专栏数据结构与算法

codevs 1213 解的个数

1213 解的个数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 已知整数x...

35140
来自专栏Java开发者杂谈

最大公约数的算法

算法的原理:   对于辗转相除法:i和j的最大公约数,也就是i和j都能够除断它。换句话讲,就是i比j的n倍多的那个数k(i = j*n + k,即i % j =...

35480
来自专栏Golang语言社区

Go语言归并排序算法实现

算法导论的伪代码: MERGE 函数是合并两个已经排好序的序列。 下面的输入参数:A是一个数组,p,q和r是数组下标,满足 p<=q<=r。下面的函数假设子数组...

52380
来自专栏GreenLeaves

C# String.Format的格式限定符与Format方法将多个对象格式化一个字符串原理

Format方法将多个对象格式化成一个字符串Format方法解析格式字符串的原理:

16920
来自专栏云霄雨霁

删数问题

26300

扫码关注云+社区

领取腾讯云代金券