Golang 计数排序算法
最后修改于 2025 年 3 月 9 日
本教程将介绍 Golang 中的计数排序算法。我们将定义它，展示用于排序数字和文本的示例，并将其与快速排序进行比较。
算法 是解决问题或执行任务的清晰、分步的方法。它是程序处理和管理数据的基础。
排序 将数据按特定顺序排列，例如升序或降序。它在计算中对于组织和检索数据至关重要。
常用排序算法
以下是一些著名的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 计数排序
计数排序算法
计数排序是一种非比较排序方法。它计算输入中每个元素出现的次数，然后使用该计数将元素放置在其正确的排序位置。
对于小范围的整数来说它速度很快，但需要额外的内存来存储计数数组。与比较排序不同，它不直接比较元素。
计数排序示例
这是计数排序在 Golang 中对整数的实现。
counting_sort.go
package main
import "fmt"
func countingSort(arr []int) []int {
if len(arr) == 0 {
return arr
}
maxVal := arr[0]
for _, num := range arr {
if num > maxVal {
maxVal = num
}
}
count := make([]int, maxVal+1)
for _, num := range arr {
count[num]++
}
sorted := []int{}
for i := 0; i < len(count); i++ {
for count[i] > 0 {
sorted = append(sorted, i)
count[i]--
}
}
return sorted
}
func main() {
arr := []int{4, 2, 2, 8, 3, 3, 1}
sorted := countingSort(arr)
fmt.Println("Sorted array:", sorted)
}
此代码使用计数排序以升序对整数切片进行排序。
$ go run counting_sort.go Sorted array: [1 2 2 3 3 4 8]
对文本数据进行排序
计数排序也可以对文本进行排序，例如字符串中的字符。这是一个示例
counting_sort_text.go
package main
import "fmt"
func countingSortText(text string) string {
if len(text) == 0 {
return text
}
maxVal := int(rune(text[0]))
for _, char := range text {
if int(char) > maxVal {
maxVal = int(char)
}
}
count := make([]int, maxVal+1)
for _, char := range text {
count[int(char)]++
}
sorted := []rune{}
for i := 0; i < len(count); i++ {
for count[i] > 0 {
sorted = append(sorted, rune(i))
count[i]--
}
}
return string(sorted)
}
func main() {
text := "counting"
sorted := countingSortText(text)
fmt.Println("Sorted text:", sorted)
}
此代码使用计数排序以升序对字符串中的字符进行排序。
$ go run counting_sort_text.go Sorted text: cginnottu
降序排序
要按降序排序，我们可以在计数排序中反转输出循环。
counting_sort_desc.go
package main
import "fmt"
func countingSortDesc(arr []int) []int {
if len(arr) == 0 {
return arr
}
maxVal := arr[0]
for _, num := range arr {
if num > maxVal {
maxVal = num
}
}
count := make([]int, maxVal+1)
for _, num := range arr {
count[num]++
}
sorted := []int{}
for i := len(count) - 1; i >= 0; i-- {
for count[i] > 0 {
sorted = append(sorted, i)
count[i]--
}
}
return sorted
}
func main() {
arr := []int{4, 2, 2, 8, 3, 3, 1}
sorted := countingSortDesc(arr)
fmt.Println("Sorted array (descending):", sorted)
}
此代码以降序对整数切片进行排序。
$ go run counting_sort_desc.go Sorted array (descending): [8 4 3 3 2 2 1]
与快速排序的比较
计数排序在小整数范围内表现出色，运行时间为 O(n + k)，其中 k 是值的范围。快速排序是一种比较排序方法，平均运行时间为 O(n log n)，并且能更好地处理更大的数据集。
基准测试示例
此示例比较了计数排序和快速排序的性能。
benchmark.go
package main
import (
"fmt"
"math/rand"
"time"
)
func countingSort(arr []int) []int {
if len(arr) == 0 {
return arr
}
maxVal := arr[0]
for _, num := range arr {
if num > maxVal {
maxVal = num
}
}
count := make([]int, maxVal+1)
for _, num := range arr {
count[num]++
}
sorted := []int{}
for i := 0; i < len(count); i++ {
for count[i] > 0 {
sorted = append(sorted, i)
count[i]--
}
}
return sorted
}
func quickSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
pivot := arr[len(arr)/2]
left, middle, right := []int{}, []int{}, []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)
}
}
return append(append(quickSort(left), middle...), quickSort(right)...)
}
func main() {
rand.Seed(time.Now().UnixNano())
data := make([]int, 10000)
for i := range data {
data[i] = rand.Intn(1000)
}
start := time.Now()
countingSort(append([]int{}, data...))
fmt.Printf("Counting sort time: %.6f seconds\n", time.Since(start).Seconds())
start = time.Now()
quickSort(append([]int{}, data...))
fmt.Printf("Quick sort time: %.6f seconds\n", time.Since(start).Seconds())
}
此基准测试在 10,000 个随机整数上测试了这两种算法。计数排序在小范围内可能表现更好，但快速排序的可扩展性更强。
来源
我们已经探讨了 Golang 中的计数排序，并将其与快速排序进行了比较。