Go 语言气泡排序
最后修改于 2025年3月8日
本教程将探讨 Go 语言中的气泡排序算法。我们将演示如何对数字和文本数据进行升序和降序排序，并将其与快速排序进行基准测试。
一个 算法 是一个定义良好的步骤序列，旨在高效地解决问题或完成任务。在编程中，算法是计算逻辑的支柱。
排序 是指将数据集合组织成特定的序列，例如升序（从小到大）或降序（从大到小）。它是从数据库到用户界面的许多应用程序中的一项关键操作。
常用排序算法
以下是一些广泛认可的排序算法：
- 气泡排序
- 快速排序
- 归并排序
- 插入排序
- 选择排序
气泡排序算法
气泡排序是一种简单的排序方法，它遍历列表，比较相邻的项，如果顺序错误则交换它们。它之所以得名，是因为较大的元素会像气泡一样“冒”到末尾。
这个过程会重复进行，直到不再需要交换为止，这表示列表已排序。虽然简单，但由于其二次时间复杂度，它对于大型数据集来说不是最快的。
气泡排序示例
下面是一个用于数字的 Go 语言气泡排序实现。
package main
import "fmt"
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n; i++ {
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
func main() {
nums := []int{64, 34, 25, 12, 22, 11, 90}
bubbleSort(nums)
fmt.Println("Sorted array:", nums)
}
此代码定义了一个 bubbleSort 函数，该函数对整数切片进行升序排序。外循环运行 n 次，其中 n 是切片的长度。
内循环比较相邻的元素，如果左边的元素大于右边的元素，则交换它们。执行后，数组将从小到大排序。
$ go run bubble_sort.go Sorted array: [11 12 22 25 34 64 90]
对文本数据进行排序
气泡排序也可以处理字符串。这里有一个对文本进行升序和降序排序的例子。
package main
import "fmt"
func bubbleSort(arr []string, reverse bool) {
n := len(arr)
for i := 0; i < n; i++ {
for j := 0; j < n-i-1; j++ {
if (!reverse && arr[j] > arr[j+1]) || (reverse && arr[j] < arr[j+1]) {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
func main() {
words := []string{"banana", "apple", "cherry", "date"}
bubbleSort(words, false)
fmt.Println("Ascending order:", words)
bubbleSort(words, true)
fmt.Println("Descending order:", words)
}
bubbleSort 函数现在接受一个 reverse 布尔值来切换排序方向。对于升序，如果左边的字符串按字母顺序大于右边的字符串，则进行交换。
对于降序，如果左边的字符串小于右边的字符串，则进行交换。这种灵活性使其适用于 Go 程序中对名称、标签或其他文本数据进行排序。
$ go run bubble_sort_text.go Ascending order: [apple banana cherry date] Descending order: [date cherry banana apple]
比较气泡排序与快速排序
气泡排序的简单性是有代价的——它对于大型数据集来说很慢，时间复杂度为 O(n²)。快速排序的平均复杂度为 O(n log n)，速度要快得多。
下面的示例使用大型随机数据集对这两种算法进行了基准测试，以突出它们在 Go 语言中的性能差异。
package main
import (
"fmt"
"math/rand"
"time"
)
func bubbleSort(arr []int) {
n := len(arr)
for i := 0; i < n; i++ {
for j := 0; j < n-i-1; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
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)
}
bubbleData := make([]int, len(data))
copy(bubbleData, data)
start := time.Now()
bubbleSort(bubbleData)
bubbleTime := time.Since(start)
quickData := make([]int, len(data))
copy(quickData, data)
start = time.Now()
quickSort(quickData)
quickTime := time.Since(start)
fmt.Printf("Bubble Sort time: %.6f seconds\n", bubbleTime.Seconds())
fmt.Printf("Quick Sort time: %.6f seconds\n", quickTime.Seconds())
}
此代码生成 1000 个随机整数并计时这两种排序方法。bubbleSort 函数会就地修改切片，而 quickSort 则使用递归返回一个新的排序后的切片。
快速排序围绕枢轴对数据进行分区，递归地对子列表进行排序，从而使其更有效。基准测试通常显示气泡排序花费的时间要长得多——通常是 10 倍或更多。
了解这些差异有助于开发人员为他们的需求选择正确的算法，平衡实际 Go 应用程序中的简单性与性能。
来源
本教程介绍了 Go 语言中的气泡排序，包括数字和文本的示例，以及与快速排序的性能比较。