Go 基数排序
最后修改于 2025年3月8日
本教程将在 Go 中实现并解释基数排序算法，重点关注高效地对数值和文本数据进行排序。
一个算法是为了解决问题或执行任务而精心设计的精确步骤序列。它是编程的核心概念，驱动计算解决方案。
排序涉及将数据安排成预定义的顺序，例如升序或降序。它提高了数据访问速度，并支持搜索引擎等应用程序中的分析。
常用排序算法
以下是一些著名的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 基数排序
基数排序
基数排序是一种非比较排序算法，它通过处理数据中的每个数字或字符来排序，从最低有效位到最高有效位。它在处理整数和固定长度字符串方面表现出色。
与快速排序等基于比较的排序不同，基数排序使用计数来将元素分发到存储桶中，在特定条件下提供线性时间复杂度。
基数排序示例
这是一个 Go 整数基数排序实现。
package main
import "fmt"
func countingSort(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
for i := 0; i < n; i++ {
index := arr[i] / exp
count[index%10]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {
index := arr[i] / exp
output[count[index%10]-1] = arr[i]
count[index%10]--
}
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
func radixSort(arr []int) {
maxNum := arr[0]
for _, num := range arr {
if num > maxNum {
maxNum = num
}
}
for exp := 1; maxNum/exp > 0; exp *= 10 {
countingSort(arr, exp)
}
}
func main() {
arr := []int{170, 45, 75, 90, 802, 24, 2, 66}
radixSort(arr)
fmt.Println("Sorted array:", arr)
}
此代码使用 `countingSort` 作为辅助函数，按每个数字进行排序，从最低有效位开始。`exp` 变量跟踪当前数字位（1、10、100 等）。
`radixSort` 函数查找最大数字以确定要处理的位数。它就地修改数组，有效地将其按升序排序。
$ go run radix_sort.go Sorted array: [2 24 45 66 75 90 170 802]
对文本数据进行排序
基数排序也可以对字符串进行排序。下面是一个对字符串进行升序和降序排序的示例。
package main
import "fmt"
func countingSortStrings(arr []string, index int) {
n := len(arr)
output := make([]string, n)
count := make([]int, 256)
for i := 0; i < n; i++ {
char := byte(0)
if index < len(arr[i]) {
char = arr[i][index]
}
count[char]++
}
for i := 1; i < 256; i++ {
count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {
char := byte(0)
if index < len(arr[i]) {
char = arr[i][index]
}
output[count[char]-1] = arr[i]
count[char]--
}
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
func radixSortStrings(arr []string, reverse bool) {
maxLen := 0
for _, s := range arr {
if len(s) > maxLen {
maxLen = len(s)
}
}
for i := maxLen - 1; i >= 0; i-- {
countingSortStrings(arr, i)
}
if reverse {
for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
arr[i], arr[j] = arr[j], arr[i]
}
}
}
func main() {
arr := []string{"apple", "banana", "kiwi", "mango", "cherry"}
radixSortStrings(arr, false)
fmt.Println("Ascending order:", arr)
radixSortStrings(arr, true)
fmt.Println("Descending order:", arr)
}
`countingSortStrings` 函数根据特定的字符位置进行排序，使用 256 个槽的计数数组来处理 ASCII 字符。它隐式地用空字节填充较短的字符串。
`radixSortStrings` 函数从右到左处理字符，以确保正确的字典顺序。`reverse` 标志在排序后交换元素以实现降序。
这对于在需要文本数据组织的 Go 应用程序中对名称、ID 或标签进行排序非常实用。
$ go run radix_sort_strings.go Ascending order: [apple banana cherry kiwi mango] Descending order: [mango kiwi cherry banana apple]
基数排序与快速排序的比较
基数排序在处理固定大小的数据（如整数或字符串）时表现出色，其时间复杂度为 O(nk)，其中 k 是数字或字符的数量。快速排序的平均时间复杂度为 O(n log n)，用途更广。
下面的基准测试比较了它们在 Go 中处理大型整数数据集时的性能，突出了它们的优势。
package main
import (
"fmt"
"math/rand"
"time"
)
func countingSort(arr []int, exp int) {
n := len(arr)
output := make([]int, n)
count := make([]int, 10)
for i := 0; i < n; i++ {
index := arr[i] / exp
count[index%10]++
}
for i := 1; i < 10; i++ {
count[i] += count[i-1]
}
for i := n - 1; i >= 0; i-- {
index := arr[i] / exp
output[count[index%10]-1] = arr[i]
count[index%10]--
}
for i := 0; i < n; i++ {
arr[i] = output[i]
}
}
func radixSort(arr []int) {
maxNum := arr[0]
for _, num := range arr {
if num > maxNum {
maxNum = num
}
}
for exp := 1; maxNum/exp > 0; exp *= 10 {
countingSort(arr, exp)
}
}
func quickSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
pivot := arr[len(arr)/2]
left := []int{}
middle := []int{}
right := []int{}
for _, x := range arr {
if x < pivot {
left = append(left, x)
} else if x == pivot {
middle = append(middle, x)
} else {
right = append(right, x)
}
}
left = quickSort(left)
right = quickSort(right)
return append(append(left, middle...), right...)
}
func main() {
rand.Seed(time.Now().UnixNano())
arr := make([]int, 10000)
for i := range arr {
arr[i] = rand.Intn(10000)
}
radixData := make([]int, len(arr))
copy(radixData, arr)
start := time.Now()
radixSort(radixData)
radixTime := time.Since(start)
quickData := make([]int, len(arr))
copy(quickData, arr)
start = time.Now()
quickSort(quickData)
quickTime := time.Since(start)
fmt.Printf("Radix Sort time: %.6f seconds\n", radixTime.Seconds())
fmt.Printf("Quick Sort time: %.6f seconds\n", quickTime.Seconds())
}
此基准测试创建了 10,000 个随机整数。`radixSort` 使用基于数字的计数进行就地排序，而 `quickSort` 通过递归地划分数据来返回一个新的切片。
对于数字范围较小的整数，基数排序通常优于快速排序，但快速排序更能适应各种数据类型。结果各不相同，但在此数据集上，基数排序通常略胜一筹。
来源
本教程在 Go 中实现了基数排序，涵盖了数字和字符串，并与快速排序进行了比较以获取性能见解。