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

基数排序是一种按照数字对元素进行排序的算法。它具有线性时间复杂度，并且适用于排序大量数据。它使用计数排序来计算数字的频率。

计数排序是一种有效的排序算法，适用于输入是一定范围内的整数。它统计输入中每个唯一元素的出现次数，并使用这些信息来获得每个元素的正确位置。

子程序是程序的一个函数，能够完成特定的任务，并且可以在程序中根据需要进行重复调用。

语法

func len(v Type) int

len()方法返回任何参数的长度。它接受一个输入，即想要知道长度的数据类型变量，并返回该变量的长度作为整数值。

func make ([] type, size, capacity)

在Go语言中，make函数用于生成数组/映射。它接收的参数包括要生成的变量类型，以及其大小和容量。

func range(variable)

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

步骤

• 步骤 1 − 该程序根据需要导入fmt、main和math等必要的软件包

• 步骤 2 − 创建一个名为find_max的函数，用于找到数组中的最大元素

示例1：使用重复

在此示例中，我们将编写一个使用count sort作为子程序的Go语言程序来实现基数排序，其中counting sort计算每个数字，而基数排序重复调用count sort来对数组进行排序。

package main

import (
   "fmt"
   "math"
)

func findmaximum(array []int) int {
   maximum := math.MinInt64
   for _, number := range array {
      if number > maximum {
         maximum = number
      }
   }
   return maximum
}

func countsort(array []int, exp int) {
   m := len(array)
   output := make([]int, m)
   count := make([]int, 10)

   for a := 0; a < 10; a++ {
      count[a] = 0
   }

   for a := 0; a < m; a++ {
      index := (array[a] / exp) % 10
      count[index]++
   }

   for a := 1; a < 10; a++ {
      count[a] += count[a-1]
   }

   for a := m - 1; a >= 0; a-- {
      index := (array[a] / exp) % 10
      output[count[index]-1] = array[a]
      count[index]--
   }

   for a := 0; a < m; a++ {
      array[a] = output[a]
   }
}

func radsorting(array []int) {
   maximum := findmaximum(array)

   for exp := 1; maximum/exp > 0; exp *= 10 {
      countsort(array, exp)
   }
}

func main() {
   array := []int{10, 12, 18, 02, 04, 95, 72, 62}
   fmt.Println("The Unsorted array is:", array)
   radsorting(array)
   fmt.Println("After sorting:", array)
}

输出

Original aray is :  [10 12 18 2 4 95 72 62]
The Sorted array: [2 4 10 12 18 62 72 95]

示例2：使用队列的迭代实现

在这个示例中，我们将编写一个Go语言程序，使用计数排序作为子程序来实现基数排序，该子程序涉及从最低有效位到最高有效位的每个数字的处理。

package main

import (
   "fmt"
)

type Queue struct {
   elements []int
}

func (q *Queue) Enqueue(element int) {
   q.elements = append(q.elements, element)
}

func (q *Queue) Dequeue() int {
   element := q.elements[0]
   q.elements = q.elements[1:]
   return element
}

func (q *Queue) IsEmpty() bool {
   return len(q.elements) == 0
}

func getmaximum(arr []int) int {
   max := arr[0]
   for _, num := range arr {
      if num > max {
         max = num
      }
   }
   return max
}

func radixSorting(arr []int) []int {
   max := getmaximum(arr)
   digits := 0
   for max > 0 {
      max /= 10
      digits++
   }

   for i := 0; i < digits; i++ {
      queues := make([]*Queue, 10)
      for j := 0; j < 10; j++ {
         queues[j] = &Queue{elements: []int{}}
      }

      for _, num := range arr {
         digit := (num / Pow(10, i)) % 10
         queues[digit].Enqueue(num)
      }

      index := 0
      for j := 0; j < 10; j++ {
         for !queues[j].IsEmpty() {
            arr[index] = queues[j].Dequeue()
            index++
         }
      }
   }

   return arr
}

func Pow(base, exp int) int {
   result := 1
   for exp > 0 {
      if exp&1 != 0 {
         result *= base
      }
      base *= base
      exp >>= 1
   }
   return result
}

func main() {
   arr := []int{110, 223, 45, 50, 812, 84, 21, 17}
   sorted := radixSorting(arr)
   fmt.Println("Array after sorting:", sorted)
}

输出

Array after sorting : [17 21 45 50 84 110 223 812]

示例3：原地基数排序

在这个示例中，我们将编写一个Go语言程序，使用计数排序作为子程序来实现基数排序。在这种方法中，排序是原地进行的，这意味着它不需要额外空间与输入成比例。

package main

import (
   "fmt"
)

func getMax(array []int) int {
   max := array[0]
   for _, num := range array {
      if num > max {
         max = num
      }
   }
   return max
}

func countingSort(array []int, exp int) {
   n := len(array)
   output := make([]int, n)
   count := make([]int, 10)

   for i := 0; i < n; i++ {
      index := (array[i] / exp) % 10
      count[index]++
   }

   for i := 1; i < 10; i++ {
      count[i] += count[i-1]
   }

   for i := n - 1; i >= 0; i-- {
      index := (array[i] / exp) % 10
      output[count[index]-1] = array[i]
      count[index]--
   }

   for i := 0; i < n; i++ {
      array[i] = output[i]
   }
}

func radixSort(arr []int) {
   max := getMax(arr)

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

func main() {
   array := []int{15, 65, 32, 34, 435, 87, 56, 86}
   radixSort(array)
   fmt.Println("Array after sorting :", array)
}

输出

Array after sorting: [15 32 34  56 65 86 87 435]

结论

在本文中，我们检查了如何在未排序的数组上执行基数排序，并使用不同的方法使用golanguage打印排序后的数组。我们探讨了使用重复、迭代和原地基数排序实现此程序。