Go 插入排序
最后修改于 2025年3月8日
本教程将介绍 Go 中的插入排序算法，展示其在升序和降序排列数字和文本数据方面的用法，并与快速排序进行基准测试。
一个算法是一组精确的步骤，旨在高效地解决问题或完成任务。它是编程的核心概念，支持数据处理和自动化。
排序是指将数据按特定顺序排列，例如升序或降序。它对于优化数据检索和支持分析任务至关重要。
常用排序算法
以下是一些著名的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
插入排序
插入排序是一种简单的算法，它一次一个元素地逐步构建一个已排序的数组。它对于小型或近乎排序的数据集非常高效。
其时间复杂度为 O(n²)，对于大型数据集效率不高，但其简单性和原地操作使其在在线排序等特定用例中具有价值。
插入排序示例
这里是适用于数字和字符串的插入排序的 Go 实现。
package main
import "fmt"
func insertionSort(arr []int) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func insertionSortStrings(arr []string) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func insertionSortDesc(arr []int) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] < key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func insertionSortStringsDesc(arr []string) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] < key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
func main() {
numbers := []int{12, 11, 13, 5, 6}
words := []string{"apple", "banana", "cherry", "date"}
insertionSort(numbers)
fmt.Println("Sorted numbers (ascending):", numbers)
insertionSortStrings(words)
fmt.Println("Sorted words (ascending):", words)
insertionSortDesc(numbers)
fmt.Println("Sorted numbers (descending):", numbers)
insertionSortStringsDesc(words)
fmt.Println("Sorted words (descending):", words)
}
insertionSort 和 insertionSortStrings 函数按升序对整数和字符串进行排序，而 insertionSortDesc 和 insertionSortStringsDesc 则按降序排序。
每个函数都原地操作，通过移动元素将当前键插入到其正确的位置。这展示了 Go 针对特定类型的方法，可以高效地处理数字和文本数据。
$ go run insertion_sort.go Sorted numbers (ascending): [5 6 11 12 13] Sorted words (ascending): [apple banana cherry date] Sorted numbers (descending): [13 12 11 6 5] Sorted words (descending): [date cherry banana apple]
说明
插入排序会遍历数组，将第一个元素视为已排序。对于每个后续元素，它会将较大的（或较小的，用于降序）元素向右移动。
func insertionSort(arr []int) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
insertionSort 函数通过将每个键与前面的元素进行比较，并在需要时移动元素，直到键找到合适位置，从而实现升序排序。
func insertionSortDesc(arr []int) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] < key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
insertionSortDesc 函数通过反转比较来实现降序排序，它会移动较小的元素为键腾出空间。
插入排序与快速排序的比较
插入排序的 O(n²) 复杂度适用于小型或部分排序的数据，而快速排序的平均 O(n log n) 效率则在大型数据集上表现出色。此基准测试突显了它们在 Go 中的差异。
package main
import (
"fmt"
"math/rand"
"time"
)
func insertionSort(arr []int) {
for i := 1; i < len(arr); i++ {
key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {
arr[j+1] = arr[j]
j--
}
arr[j+1] = key
}
}
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())
data := make([]int, 1000)
for i := range data {
data[i] = rand.Intn(1000)
}
insertData := make([]int, len(data))
copy(insertData, data)
start := time.Now()
insertionSort(insertData)
insertTime := time.Since(start)
quickData := make([]int, len(data))
copy(quickData, data)
start = time.Now()
quickSort(quickData)
quickTime := time.Since(start)
fmt.Printf("Insertion Sort Time: %.6f seconds\n", insertTime.Seconds())
fmt.Printf("Quick Sort Time: %.6f seconds\n", quickTime.Seconds())
}
此基准测试在 1,000 个随机整数上测试了这两种算法。插入排序原地修改数组，而快速排序通过递归和分区创建新的切片。
由于其对数缩放的特性，快速排序在大数据集上的性能通常显著优于插入排序。插入排序的优势在于其简单性和在小型或近乎排序数据上的性能。
来源
本教程介绍了 Go 中的插入排序，包括数字和文本的示例，并与快速排序进行了基准测试。