Go 快速排序
最后修改于 2025年3月8日
本教程将探讨 Go 中的快速排序算法，展示如何按升序和降序对数字和文本数据进行排序。
一个 算法 是一个结构化的步骤序列，用于高效地解决问题或执行任务。它是编程的基石，指导着计算逻辑。
排序 是指将数据组织成特定的序列，例如升序（从小到大）或降序（从大到小）。这对于数据检索和呈现等任务至关重要。
常用排序算法
以下是一些著名的排序算法
- 快速排序
- 归并排序
- 气泡排序
- 插入排序
- 选择排序
快速排序算法
快速排序是一种分治算法，它选择一个基准元素并将数组围绕它进行分区。小于基准的元素放在左边，大于基准的元素放在右边。
子数组被递归地排序，最终得到一个完全排序的数组。其平均时间复杂度为 O(n log n)，对于大多数数据集来说都很高效，尽管最坏情况是 O(n²)。
快速排序示例
下面是一个用于数字和字符串的 Go 快速排序实现。
quick_sort.go
package main
import "fmt"
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 quickSortStrings(arr []string) []string {
if len(arr) <= 1 {
return arr
}
pivot := arr[len(arr)/2]
left := []string{}
middle := []string{}
right := []string{}
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 = quickSortStrings(left)
right = quickSortStrings(right)
return append(append(left, middle...), right...)
}
func main() {
numbers := []int{3, 6, 8, 10, 1, 2, 1}
sortedNumbers := quickSort(numbers)
fmt.Println("Sorted numbers:", sortedNumbers)
words := []string{"banana", "apple", "cherry", "date"}
sortedWords := quickSortStrings(words)
fmt.Println("Sorted words:", sortedWords)
}
quickSort 函数用于对整数进行排序，而 quickSortStrings 用于处理字符串。两者都使用中间基准并通过递归对数据进行分区。
结果是一个新的升序排序的切片。这种方法利用了 Go 的类型系统，以简洁的方式确保了对不同数据类型的灵活性。
$ go run quick_sort.go Sorted numbers: [1 1 2 3 6 8 10] Sorted words: [apple banana cherry date]
降序排序
以下是如何在 Go 中调整快速排序以实现降序排序。
quick_sort_desc.go
package main
import "fmt"
func quickSortDesc(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 = quickSortDesc(left)
right = quickSortDesc(right)
return append(append(left, middle...), right...)
}
func quickSortStringsDesc(arr []string) []string {
if len(arr) <= 1 {
return arr
}
pivot := arr[len(arr)/2]
left := []string{}
middle := []string{}
right := []string{}
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 = quickSortStringsDesc(left)
right = quickSortStringsDesc(right)
return append(append(left, middle...), right...)
}
func main() {
numbers := []int{3, 6, 8, 10, 1, 2, 1}
sortedNumbersDesc := quickSortDesc(numbers)
fmt.Println("Sorted numbers (descending):", sortedNumbersDesc)
words := []string{"banana", "apple", "cherry", "date"}
sortedWordsDesc := quickSortStringsDesc(words)
fmt.Println("Sorted words (descending):", sortedWordsDesc)
}
quickSortDesc 和 quickSortStringsDesc 函数颠倒了分区逻辑——较大的元素放在左边，较小的元素放在右边——从而实现降序排序。
这种调整对于对项目进行从高到低排名等场景很有用，例如 Go 应用程序中的分数或字母顺序颠倒的列表。
$ go run quick_sort_desc.go Sorted numbers (descending): [10 8 6 3 2 1 1] Sorted words (descending): [date cherry banana apple]
将快速排序与插入排序进行比较
快速排序的平均 O(n log n) 性能优于插入排序的 O(n²)，尤其是在大型数据集上。Go 中的这个基准测试说明了这种差异。
benchmark.go
package main
import (
"fmt"
"math/rand"
"time"
)
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 insertionSort(arr []int) []int {
result := make([]int, len(arr))
copy(result, arr)
for i := 1; i < len(result); i++ {
key := result[i]
j := i - 1
for j >= 0 && key < result[j] {
result[j+1] = result[j]
j--
}
result[j+1] = key
}
return result
}
func main() {
rand.Seed(time.Now().UnixNano())
data := make([]int, 10000)
for i := range data {
data[i] = rand.Intn(1000)
}
quickData := make([]int, len(data))
copy(quickData, data)
start := time.Now()
quickSort(quickData)
quickTime := time.Since(start)
insertData := make([]int, len(data))
copy(insertData, data)
start = time.Now()
insertionSort(insertData)
insertTime := time.Since(start)
fmt.Printf("Quick Sort time: %.6f seconds\n", quickTime.Seconds())
fmt.Printf("Insertion Sort time: %.6f seconds\n", insertTime.Seconds())
}
此代码生成 10,000 个随机整数并计时两种算法。快速排序使用递归和分区，而插入排序逐个移动元素。
快速排序通常完成得更快——通常快一个数量级——因为它具有对数缩放。插入排序虽然更简单，但在处理大型数据时会遇到困难，因此在这里不太实用。
这些比较有助于开发人员根据 Go 项目中的数据集大小和性能需求来选择算法。
来源
本教程在 Go 中解释了快速排序，并提供了升序和降序排序的示例，以及与插入排序的基准测试。