用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("待排序的数组为：", arr)
   sorted := mergeSort(arr)
   fmt.Println("排序后的数组为：", sorted)
}

输出

待排序的数组为： [5 2 6 3 1 4]
排序后的数组为： [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("给定的未排序数组为:", arr)
   sorted := mergeSort(arr)
   fmt.Println("得到的排序数组为:", sorted)
}

输出

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

示例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)
}

输出

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

结论

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