Golang 使用桶排序作为子程序来实现基数排序

子程序是程序的一部分，用于执行特定任务，并可以根据需求和用途重复调用。当调用子程序时，程序会切换到该程序并执行其中的指令。基数排序是一种按数字对元素进行排序的算法。它具有线性时间复杂度，并用于对大量数据进行排序。它使用计数排序来计算数字的频率。在这个 Golang 文章中，我们将编写程序来实现基数排序，使用桶排序作为子程序。

语法

func len(v Type) int

使用len()函数来确定任何参数的长度。它接受一个输入并返回整数值，即变量的长度。

func make ([] type, size, capacity)

在Go语言中，make函数用于构建数组/映射。它接收作为参数的变量类型，以及它的大小和容量。

func range(variable)

range函数可以迭代任何数据类型。要使用它，我们必须首先放置range关键字，然后放上我们要迭代的数据类型，循环将一直迭代到变量的最后一个元素为止。

步骤

• 步骤1 - 创建一个bucketSort函数。

• 步骤2 - 找到数组的最大元素。

• 步骤3 - 对于每个数字位置，进行基数排序。

• 步骤4 - 使用LSD方法实现基数排序。

• 步骤5 - 使用迭代方法实现基数排序。

示例1：最低有效位

在此示例中，我们将编写一个Go语言程序，使用桶排序作为子程序来实现基数排序。在这种方法中，元素根据数字分布在桶中，并在每个数字的位置上按原始顺序重构。

package main

import (
   "fmt"
   "math"
)

func main() {
   array := []int{10, 14, 2, 43, 65, 76, 23, 674}

   fmt.Println("Before sorting :", array)
   radixSortLSD(array)
   fmt.Println("After sorting :", array)
}

func bucketSort(arr []int, exp int) {
   n := len(arr)
   buckets := make([][]int, 10)
   for i := 0; i < 10; i++ {
      buckets[i] = make([]int, 0)
   }

   for i := 0; i < n; i++ {
      digit := (arr[i] / exp) % 10
      buckets[digit] = append(buckets[digit], arr[i])
   }

   index := 0
   for i := 0; i < 10; i++ {
      for j := 0; j < len(buckets[i]); j++ {
         arr[index] = buckets[i][j]
         index++
      }
   }
}

func radixSortLSD(arr []int) {
   max := int(math.Inf(-1))
   for _, num := range arr {
      if num > max {
         max = num
      }
   }

   exp := 1
   for exp <= max {
      bucketSort(arr, exp)
      exp *= 10
   }
}

输出

Before sorting : [10 14 2 43 65 76 23 674]
 After sorting : [2 10 14 23 43 65 76 674]

示例2：使用迭代

在这个示例中，我们将编写一个Go语言程序，使用桶排序作为子程序来实现基数排序。在这种方法中，元素根据其数字逐步分配到桶中。

package main

import (
   "fmt"
   "math"
)

func bucketSort(arr []int, exp int) {
   n := len(arr)
   buckets := make([][]int, 10)
   for i := 0; i < 10; i++ {
      buckets[i] = make([]int, 0)
   }

   for i := 0; i < n; i++ {
      digit := (arr[i] / exp) % 10
      buckets[digit] = append(buckets[digit], arr[i])
   }

   index := 0
   for i := 0; i < 10; i++ {
      for j := 0; j < len(buckets[i]); j++ {
         arr[index] = buckets[i][j]
         index++
      }
   }
}

func radixSortIterative(arr []int) {
   max := int(math.Inf(-1))
   for _, num := range arr {
      if num > max {
         max = num
      }
   }

   for exp := 1; max/exp > 0; exp *= 10 {
      bucketSort(arr, exp)
   }
}

func main() {
   array := []int{11, 15, 1, 42, 64, 78, 23, 674}

   fmt.Println("Before Sorting:", array)     
   radixSortIterative(array)
   fmt.Println("After sorting :", array)
}

输出

Before Sorting: [11 15 1 42 64 78 23 674]
After sorting : [1 11 15 23 42 64 78 674]

结论

在本文中，我们检查了如何使用桶排序作为go语言中子程序来执行基数排序。我们探索了使用迭代和LSD实现这个程序的方式。