使用Golang编写的基数排序算法

本文介绍如何使用最小有效位和最大有效位来实现基数排序。基数排序是一种排序算法，它通过将元素分组来排序，其中分组的依据是它们的个位数或位数的位置。它是一种线性时间排序算法，其时间复杂度为 O(nk)。

使用最小有效位

在这种方法中，我们将编写一个Go语言程序，通过使用最小有效位来实现基数排序。LSD按照从右到左比较它们的个位数来对元素进行排序。

算法

• 步骤1 - 首先需要导入 fmt 包。然后创建一个名为 radixSortMSD() 的函数来对数组进行排序。

• 步骤2 - 在函数内部创建一个新的数组。使用 for 循环遍历数组并将数组的最大元素存储在一个变量中。

• 步骤3 - 现在，初始化一个 count 数组来跟踪具有特定数字的元素数。

• 步骤4 - 遍历数组并为每个元素对应的数字递增计数。

• 步骤5 - 修改计数数组以存储每个元素在输出数组中的实际位置。按照计数数组指定的顺序从输入数组复制元素到输出数组中。

• 步骤6 - 更新输入数组以排序后的输出数组，并返回已排序的数组。

• 步骤7 - 开始 main() 函数。在 main() 函数内部初始化一个数组并对其进行赋值。然后调用 radixSort() 函数并将数组作为参数传递给函数。

• 步骤8 - 将函数获得的结果存储在变量中，并在屏幕上打印它。

示例

package main

import "fmt"

func radixSortLSD(arr []int) []int {
   max := arr[0]
   for i := 1; i < len(arr); i++ {
      if arr[i] > max {
         max = arr[i]
      }
   }
   exp := 1
   for max/exp > 0 {
      count := make([]int, 10)
      for i := 0; i < len(arr); i++ {
         count[(arr[i]/exp)%10]++
      }
      for i := 1; i < 10; i++ {
         count[i] += count[i-1]
      }
      Output := make([]int, len(arr))
      for i := len(arr) - 1; i >= 0; i-- {
         Output[count[(arr[i]/exp)%10]-1] = arr[i]
         count[(arr[i]/exp)%10]--
      }
      for i := 0; i < len(arr); i++ {
         arr[i] = Output[i]
      }
      exp *= 10
   }
   return arr
}

func main() {
   arr := []int{15, 31, 42, 20, 9}
   fmt.Println("The unsorted array is:", arr)
   result :=radixSortLSD(arr)
   fmt.Println("The sorted array is:", result)
}

输出

未排序的数组为：[15 31 42 20 9]
排序后的数组为：[9 15 20 31 42]

使用最大有效位

在这种方法中，我们将编写一个Go语言程序，使用基数排序通过使用最大有效位对数组进行排序，并使用以下语法来实现。

语法

func len(v Type) int

len() 函数用于获取任何参数的长度。它接受一个数据类型变量作为参数，我们希望找到此变量的长度，并返回整数值，该值是变量的长度。

算法

• 步骤 1 − 首先，我们需要导入 fmt package。然后我们创建两个名为radixSortMSD()和radixSortMSDHelper()的函数。

• 步骤 2 − radixSort()函数接受作为参数要排序的数组并返回排序后的数组。函数调用radixSortMSDHelper()函数。

• 步骤 3 − radixSortMSDHelper()函数接受要排序的数组以及数组中的最大元素作为参数。

• 步骤 4 − 该函数将排序后的数组返回给radixSort()函数，后者最终将数组返回给程序的主函数部分。

• 步骤 5 − 现在，开始主()函数。在其中初始化要排序的数组并为其分配值。

• 步骤 6 − 进一步调用radixSortMSD()函数，将数组作为参数传递给函数，并将结果存储在单独的变量中。

• 步骤 7 − 现在，使用fmt.Println()函数在屏幕上打印最终数组。

实例

在下面的实例中，我们将学习如何通过使用最重要的位实现基数排序来开发go语言程序。

package main

import "fmt"

func radixSortMSD(arr []int) []int {
   max := arr[0]
   for i := 1; i < len(arr); i++ {
      if arr[i] > max {
         max = arr[i]
      }
   }
   arr = radixSortMSDHelper(arr, max)
   return arr
}

func radixSortMSDHelper(arr []int, exp int) []int {
   if exp <= 0 {
      return arr
   }
   count := make([]int, 10)
   for i := 0; i < len(arr); i++ {
      count[(arr[i]/exp)%10]++
   }
   for i := 1; i < 10; i++ {
      count[i] += count[i-1]
   }
   Output := make([]int, len(arr))
   for i := len(arr) - 1; i >= 0; i-- {
      Output[count[(arr[i]/exp)%10]-1] = arr[i]
      count[(arr[i]/exp)%10]--
   }
   subarrays := make([][]int, 10)
   for i := 0; i < len(Output); i++ {
      subarrays[(Output[i]/exp)%10] = append(subarrays[(Output[i]/exp)%10], Output[i])
   }
   result := make([]int, 0)
   for i := 0; i < 10; i++ {
      if len(subarrays[i]) > 0 {
         subarrays[i] = radixSortMSDHelper(subarrays[i], exp/10)
         result = append(result, subarrays[i]...)
      }
   }
   return result
}

func main() {
   arr := []int{5, 3, 2, 15, 9}
   fmt.Println("未排序的数组为：", arr)
   result := radixSortMSD(arr)
   fmt.Println("排好序的数组为：", result)
}

输出

未排序的数组为：[5 3 2 15 9]
排好序的数组为：[2 3 5 9 15]

结论

我们已经成功编译并执行一个使用基数排序算法排序数组的Go语言程序。在这里，我们实现了两个例子。在第一个例子中，我们通过最不显著的位对数组进行排序，而在第二个例子中，我们通过最显著的位对数组进行排序。这两种方法的时间复杂度均为O(nk)。