归并排序的 Go 语言实现和优化

栏目: 编程工具 · 发布时间: 6年前

内容简介:查看完整的代码,不了解归并排序的可以查看

查看完整的代码, 点击这里

不了解归并 排序 的可以查看 百度百科的分析

归并排序的实现

基本实现

package main

import "fmt"

// 合并 [l,r] 两部分数据,mid 左半部分的终点,mid + 1 是右半部分的起点
func merge(arr []int, l int, mid int, r int) {
   // 因为需要直接修改 arr 数据,这里首先复制 [l,r] 的数据到新的数组中,用于赋值操作 
    temp := make([]int, r-l+1)
    for i := l; i <= r; i++ {
        temp[i-l] = arr[i]
    }
    
   // 指向两部分起点
    left := l
    right := mid + 1

    for i := l; i <= r; i++ {
       // 左边的点超过中点,说明只剩右边的数据
        if left > mid {
            arr[i] = temp[right-l]
            right++
        // 右边的数据超过终点,说明只剩左边的数据
        } else if right > r {
            arr[i] = temp[left-l]
            left++
       // 左边的数据大于右边的数据,选小的数字
        } else if temp[left - l] > temp[right - l] {
            arr[i] = temp[right - l]
            right++
        } else {
            arr[i] = temp[left - l]
            left++
        }
    }
}

func MergeSort(arr []int, l int, r int) {
    if l >= r {
        return
    }
  
  // 递归向下
    mid := (r + l) / 2
    MergeSort(arr, l, mid)
    MergeSort(arr, mid+1, r)
    // 归并向上
    merge(arr, l, mid, r)
}

func main() {
    arr := []int{3, 1, 2, 5, 6, 43, 4}
    MergeSort(arr, 0, len(arr)-1)

    fmt.Println(arr)
}

优化点

  • 只有左边数据的最大值大于右边数据的最小值时才需要归并

    举例:现在需要归并的左右部分为 [1,3] 和 [4,5],则不需要进行「并」的操作。而 [1,4] 和 [3,5] 则需要进行「并」为 [1,3,4,5]

  • 当二分数据到一定阶段,可以使用插入排序而不是继续向下二分

    虽然复杂度上看 nlogn 始终大于 n^2,但是都忽略了常数项,而归并的常数项大于插入排序,所以当 n 足够小时,插入排序速度更快

    以下是结合优化点的程序更改:

package main
    
import "fmt"
    
func merge(arr []int, l int, mid int, r int) {
    temp := make([]int, r-l+1)
    for i := l; i <= r; i++ {
        temp[i-l] = arr[i]
    }
    
    left := l
    right := mid + 1
    
    for i := l; i <= r; i++ {
        if left > mid {
            arr[i] = temp[right-l]
            right++
        } else if right > r {
            arr[i] = temp[left-l]
            left++
        } else if temp[left - l] > temp[right - l] {
            arr[i] = temp[right - l]
            right++
        } else {
            arr[i] = temp[left - l]
            left++
        }
    }
}
    
func MergeSort(arr []int, l int, r int) {
    // 第二步优化,当数据规模足够小的时候,可以使用插入排序
    if r - l <= 15 {
        // 对 l,r 的数据执行插入排序
        for i := l + 1; i <= r; i++ {
            temp := arr[i]
            j := i
            for ; j > 0 && temp < arr[j-1]; j-- {
                arr[j] = arr[j-1]
            }
            arr[j] = temp
        }
        return
    }
    
    mid := (r + l) / 2
    MergeSort(arr, l, mid)
    MergeSort(arr, mid+1, r)
    
    // 第一步优化,左右两部分已排好序,只有当左边的最大值大于右边的最小值,才需要对这两部分进行merge操作
    if arr[mid] > arr[mid + 1] {
        merge(arr, l, mid, r)
    }
}
    
func main() {
    arr := []int{3, 1, 2, 5, 6, 43, 4}
    MergeSort(arr, 0, len(arr)-1)
    
    fmt.Println(arr)
}

以上所述就是小编给大家介绍的《归并排序的 Go 语言实现和优化》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Effective C++

Effective C++

[美]Scott Meyers / 侯捷 / 电子工业出版社 / 2006-7 / 58.00元

《Effective C++:改善程序与设计的55个具体做法》(中文版)(第3版)一共组织55个准则,每一条准则描述一个编写出更好的C++的方式。每一个条款的背后都有具体范例支撑。第三版有一半以上的篇幅是崭新内容,包括讨论资源管理和模板(templates)运用的两个新章。为反映出现代设计考虑,对第二版论题做了广泛的修订,包括异常(exceptions)、设计模式(design patterns)......一起来看看 《Effective C++》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具