Golang 选择排序
最后修改于 2025 年 3 月 9 日
本文将探讨 Golang 中的选择排序算法。我们将对其进行定义，展示对数字和字符串进行排序的示例，并将其与快速排序进行比较。
一个 算法 是一个清晰的、分步的过程，用于解决问题或完成任务。它是编程的核心概念，指导代码如何工作。
排序 是将数据组织成特定顺序，例如升序或降序。它是计算机科学中管理和访问数据的关键技能。
常用排序算法
以下是一些常用的排序算法
- 选择排序
- 气泡排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
选择排序算法
选择排序算法会反复扫描列表的未排序部分，找出最小（或最大）的元素。然后，它将该元素与第一个未排序的位置进行交换。这个过程会一直重复，直到列表完全排序。
它易于理解和实现，但对于大型数据集来说不是最快的。
选择排序示例
下面是选择排序的 Golang 实现。它适用于切片，并可以按升序或降序排序。
selection_sort.go
package main
import "fmt"
func selectionSort(arr []interface{}, ascending bool) []interface{} {
n := len(arr)
for i := 0; i < n; i++ {
idx := i
for j := i + 1; j < n; j++ {
less := compare(arr[j], arr[idx]) < 0
if (ascending && less) || (!ascending && !less) {
idx = j
}
}
arr[i], arr[idx] = arr[idx], arr[i]
}
return arr
}
func compare(a, b interface{}) int {
switch a.(type) {
case int:
return a.(int) - b.(int)
case string:
if a.(string) < b.(string) {
return -1
} else if a.(string) > b.(string) {
return 1
}
return 0
}
return 0
}
func main() {
// Sorting numeric data
numbers := []interface{}{64, 25, 12, 22, 11}
fmt.Println("Ascending:", selectionSort(numbers, true))
fmt.Println("Descending:", selectionSort(numbers, false))
// Sorting textual data
words := []interface{}{"apple", "banana", "kiwi", "cherry"}
fmt.Println("Ascending:", selectionSort(words, true))
fmt.Println("Descending:", selectionSort(words, false))
}
selectionSort 函数接受一个 interface{} 类型的切片和一个用于排序方向的布尔值。它使用一个辅助的 compare 函数来处理整数和字符串等不同数据类型。
$ go run selection_sort.go Ascending: [11 12 22 25 64] Descending: [64 25 22 12 11] Ascending: [apple banana cherry kiwi] Descending: [kiwi cherry banana apple]
选择排序与快速排序的比较
选择排序易于编码，但对于大列表来说速度较慢，其时间复杂度为 O(n²)。快速排序采用分治策略，平均而言速度更快，为 O(n log n)。让我们对其进行基准测试。
benchmark.go
package main
import (
"fmt"
"math/rand"
"time"
)
func selectionSort(arr []int) []int {
n := len(arr)
for i := 0; i < n; i++ {
idx := i
for j := i + 1; j < n; j++ {
if arr[j] < arr[idx] {
idx = j
}
}
arr[i], arr[idx] = arr[idx], arr[i]
}
return arr
}
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, 1000)
for i := range data {
data[i] = rand.Intn(1000)
}
// Benchmark selection sort
start := time.Now()
selectionSort(append([]int{}, data...))
fmt.Printf("Selection Sort Time: %.6f seconds\n", time.Since(start).Seconds())
// Benchmark quick sort
start = time.Now()
quickSort(append([]int{}, data...))
fmt.Printf("Quick Sort Time: %.6f seconds\n", time.Since(start).Seconds())
}
此基准测试在 1000 个随机整数上对选择排序和快速排序进行测试。由于其高效的设计，快速排序通常完成得快得多。
来源
本教程涵盖了 Golang 中的选择排序，并将其与快速排序进行了比较。