Golang 实现归并排序

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

语法

func copy(dst, str[] type) int

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

func len(v Type) int

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("The given unsorted array is:", arr)
   sorted := mergeSort(arr)
   fmt.Println("The sorted array is:", sorted)
}

输出

The given unsorted array is: [5 2 6 3 1 4]
The sorted array is: [1 2 3 4 5 6]

示例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("The given unsorted array is:", arr)
   sorted := mergeSort(arr)
   fmt.Println("The obtained sorted array is:", sorted)
}

输出

The given unsorted array is: [5 2 6 3 1 4]
The obtained sorted array is: [1 2 3 4 5 6]

示例3

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

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("Unsorted array:", arr)
   c := make(chan []int)
   go mergeSort(arr, c)
   sorted := <-c
   fmt.Println("Sorted array:", sorted)
}

输出

Unsorted array: [15 21 6 30 16 43]
Sorted array: [6 15 16 21 30 43]

结论

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