Golang 实现基数排序

在本文中，我们将了解如何使用最低有效位和最高有效位来实现基数排序。基数排序是一种根据元素的个别数字或数字的位置对其进行分组的排序算法。它是一种线性时间排序算法，时间复杂度为O(nk)。

使用最低有效位

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

步骤

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

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

• 步骤3： 现在，初始化一个计数数组，以跟踪具有特定数字的元素的数量。

• 步骤4： 遍历数组，并为每个元素的相应数字增加计数。

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

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

• 步骤7： 开始main()函数。在main()函数内部，初始化一个数组并将值存储到其中。然后，调用radixSort()函数并将数组作为参数传递给函数。

• 步骤8： 将函数得到的结果存储在一个变量中，并在屏幕上打印出来。

示例

以下示例演示如何使用最低有效位开发一个Go语言程序来实现基数排序。

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

输出

The unsorted array is: [15 31 42 20 9]
The sorted array is: [9 15 20 31 42]

使用最高有效位

在这种方法中，我们将使用高级排序方法和Go语言编写一个程序来使用最高有效位（Most Significant Bit）来对数组进行排序，使用下面的语法。

语法

func len(v Type) int

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

步骤

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

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

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

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

• 步骤5 - 现在，开始main()函数。在main()内部初始化要排序的数组并为其赋值。

• 步骤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("The unsorted array is:", arr)
   result := radixSortMSD(arr)
   fmt.Println("The sorted array is:", result)
}

输出

The unsorted array is: [5 3 2 15 9]
The sorted array is: [2 3 5 9 15]

结论

我们成功地编译和执行了一个使用基数排序算法对数组进行排序的Go语言程序。这里我们实现了两个示例。在第一个示例中，我们通过最低有效位来对数组进行排序，而在第二个示例中，我们通过最高有效位来对数组进行排序。两种方法的时间复杂度都为O(nk)。