当前位置：极客教程 > Go 语言 > Go 实例 > 用Golang实现归并排序

用Golang实现归并排序

用Golang实现归并排序

在本篇Golang文章中，我们将学习如何使用三种不同的方法——递归、迭代和goroutines，在Golang中实现归并排序。归并排序是一种使用分治法对元素列表进行排序的最有效的排序算法之一。

语法

func copy(dst, str[] type) int
Go

在Go语言中，copy函数用于将源数组的值复制到目标数组，并返回复制的元素数量。它接受两个数组作为参数。

func len(v Type) int
Go

len()函数用于获取任何参数的长度。它接受一个参数作为数据类型变量，返回整数值，即变量的长度。

算法

  • 步骤1 − 首先，我们需要导入fmt包。

  • 步骤2 − 现在，定义一个名为mergeSort的函数，它接受一个整数数组作为参数，并返回排序后的数组。

  • 步骤3 − 在函数内部，如果数组的长度小于或等于1，则返回完整的数组，因为不能对数组中的单个元素进行排序。然后找到给定数组的中间点。

  • 步骤4 − 递归地在数组的左半部分上调用mergeSort()函数，并将结果存储在一个名为left的变量中。

  • 步骤5 − 类似地，再次递归地在数组的右半部分上调用mergeSort()函数，并将结果存储在一个名为right的变量中。

  • 步骤6 − 调用merge函数，并将左右数组作为输入，并返回结果。

  • 步骤7 − merge()函数接受左右两个数组作为参数，使用for循环和if条件将它们组合成一个单一的数组。

  • 步骤8 − 现在，开始main()函数。在main()内部初始化要排序的数组，并将它们打印到屏幕上。

  • 步骤9 − 进一步地，通过将初始化为参数的数组调用mergeSort()函数。将函数获得的结果存储在一个变量中，并将它们打印到屏幕上。

示例1

递归是实现归并排序的最常见方法。在这个方法中，我们将给定的数据分成两半，然后递归地对每半进行排序。然后将排序后的两个部分合并起来，实现归并排序。

package main

import "fmt"

func mergeSort(arr []int) []int {
   if len(arr) <= 1 {
      return arr
   }
   middle := len(arr) / 2
   left := mergeSort(arr[:middle])
   right := mergeSort(arr[middle:])
   return merge(left, right)
}

func merge(left, right []int) []int {
   result := make([]int, len(left)+len(right))
   i,j := 0, 0
   for k := 0; k < len(result); k++ {
      if i >= len(left) {
         result[k] = right[j]
         j++
      } else if j >= len(right) {
         result[k] = left[i]
         i++
      } else if left[i] < right[j] {
         result[k] = left[i]
         i++
      } else {
         result[k] = right[j]
         j++
      }
   }
   return result
}

func main() {
   arr := []int{5, 2, 6, 3, 1, 4}
   fmt.Println("待排序的数组为：", arr)
   sorted := mergeSort(arr)
   fmt.Println("排序后的数组为：", sorted)
}
Go

输出

待排序的数组为： [5 2 6 3 1 4]
排序后的数组为： [1 2 3 4 5 6]
Go

示例2

在本例中，我们将使用迭代变量来实现数组的归并排序。在这种方法中，我们将使用各种内置函数，例如copy()和len()，以及for循环和if条件语句来实现结果。

package main

import "fmt"

func mergeSort(arr []int) []int {
   if len(arr) <= 1 {
      return arr
   }
   size := 1
   for size < len(arr) {
      for left := 0; left < len(arr)-1; left += size * 2 {
         middle := left + size - 1
         right := min(left+size*2-1, len(arr)-1)
         merged := merge(arr[left:middle+1], arr[middle+1:right+1])
         copy(arr[left:right+1], merged)
      }
      size *= 2
   }
   return arr
}

func merge(left, right []int) []int {
   result := make([]int, len(left)+len(right))
   i, j := 0, 0
   for k := 0; k < len(result); k++ {
      if i >= len(left) {
         result[k] = right[j]
         j++
      } else if j >= len(right) {
         result[k] = left[i]
         i++
      } else if left[i] < right[j] {
         result[k] = left[i]
         i++
      } else {
         result[k] = right[j]
         j++
      }
   }
   return result
}

func min(a, b int) int {
   if a < b {
      return a
   }
   return b
}

func main() {
   arr := []int{5, 2, 6, 3, 1, 4}
   fmt.Println("给定的未排序数组为:", arr)
   sorted := mergeSort(arr)
   fmt.Println("得到的排序数组为:", sorted)
}
Go

输出

给定的未排序数组为: [5 2 6 3 1 4]
得到的排序数组为: [1 2 3 4 5 6]
Go

示例3

在这个例子中，我们将使用goroutines来实现归并排序。Goroutines可以定义为允许我们使用并发编程的轻量级线程。

package main

import "fmt"

func mergeSort(arr []int, c chan []int) {
   if len(arr) <= 1 {
      c <- arr
      return
   }
   middle := len(arr) / 2
   leftChan := make(chan []int)
   rightChan := make(chan []int)
   go mergeSort(arr[:middle], leftChan)
   go mergeSort(arr[middle:], rightChan)
   left := <-leftChan
   right := <-rightChan
   c <- merge(left, right)
}

func merge(left, right []int) []int {
   result := make([]int, len(left)+len(right))
   i, j := 0, 0
   for k := 0; k < len(result); k++ {
      if i >= len(left) {
         result[k] = right[j]
         j++
      } else if j >= len(right) {
         result[k] = left[i]
         i++
      } else if left[i] < right[j] {
         result[k] = left[i]
         i++
      } else {
         result[k] = right[j]
         j++
      }
   }
   return result
}

func main() {
   arr := []int{15, 21, 6, 30, 16, 43}
   fmt.Println("未排序数组:", arr)
   c := make(chan []int)
   go mergeSort(arr, c)
   sorted := <-c
   fmt.Println("排序数组:", sorted)
}
Go

输出

未排序数组: [15 21 6 30 16 43]
排序数组: [6 15 16 21 30 43]
Go

结论

我们已成功编译和执行了一个go语言程序来实现归并，并且示例中使用了三个程序。在第一个程序中，我们使用递归的概念来实现结果，而在第二个和第三个程序中，我们分别使用了内部库函数和goroutines。

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

Go语言 精品教程

登录

找回密码？

注册