Go Shell Sort 算法
最后修改于 2025年3月8日
本教程将讲解 Go 中的 Shell Sort 算法，演示其在升序和降序排列数字和文本数据中的应用，并与 Quick Sort 进行基准测试。
一个 算法 是为了高效地解决问题或执行任务而设计的、定义明确的步骤序列。它是编程的基石，能够实现系统化的解决方案。
排序 是将数据按特定顺序排列（如升序或降序）的行为。它对于优化各种应用中的数据访问和分析至关重要。
常用排序算法
以下是一些常用的排序算法
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- Shell Sort（希尔排序）
Shell Sort 算法
Shell Sort 通过比较和排序特定间隔（或称为步长）的元素，而不是相邻元素，来改进插入排序。它从大的步长开始，并在每次迭代中减小步长。
这种方法可以最大限度地减少所需的移动次数，从而比纯插入排序更有效。其时间复杂度根据步长序列的不同，在 O(n log n) 和 O(n²) 之间变化。
Shell Sort 示例
这是 Shell Sort 在 Go 中用于数值数据的实现示例。
package main
import "fmt"
func shellSort(arr []int) {
n := len(arr)
gap := n / 2
for gap > 0 {
for i := gap; i < n; i++ {
temp := arr[i]
j := i
for j >= gap && arr[j-gap] > temp {
arr[j] = arr[j-gap]
j -= gap
}
arr[j] = temp
}
gap /= 2
}
}
func main() {
nums := []int{12, 34, 54, 2, 3}
shellSort(nums)
fmt.Println("Sorted array:", nums)
}
shellSort 函数以升序对整数切片进行排序。它从数组长度的一半作为步长开始，并在每次迭代中将步长减半。
在每个步长内，它执行类似插入排序的操作，将较大的元素向右移动。此示例对一个小数组进行排序，展示了该算法在 Go 中的基本操作。
$ go run shell_sort.go Sorted array: [2 3 12 34 54]
对文本数据进行排序
Shell Sort 也可以排序字符串。以下是在 Go 中升序和降序排序的示例。
package main
import "fmt"
func shellSort(arr []string, reverse bool) {
n := len(arr)
gap := n / 2
for gap > 0 {
for i := gap; i < n; i++ {
temp := arr[i]
j := i
if reverse {
for j >= gap && arr[j-gap] < temp {
arr[j] = arr[j-gap]
j -= gap
}
} else {
for j >= gap && arr[j-gap] > temp {
arr[j] = arr[j-gap]
j -= gap
}
}
arr[j] = temp
}
gap /= 2
}
}
func main() {
words := []string{"apple", "banana", "cherry", "date", "elderberry"}
shellSort(words, false)
fmt.Println("Ascending order:", words)
shellSort(words, true)
fmt.Println("Descending order:", words)
}
shellSort 函数现在接受一个 reverse 布尔值来切换排序方向。对于升序，它会移动较大的字符串；对于降序，则会移动较小的字符串。
这会在原地对字符串切片进行排序，使其成为 Go 程序中文本数据（如姓名或类别）的多功能工具，其基于步长的优势提高了效率。
$ go run shell_sort_text.go Ascending order: [apple banana cherry date elderberry] Descending order: [elderberry date cherry banana apple]
Shell Sort 与 Quick Sort 的比较
Shell Sort 在处理中等规模数据时表现良好，但 Quick Sort 的平均 O(n log n) 时间复杂度通常使其在大数据集上更快。此基准测试在 Go 中对它们进行了比较。
package main
import (
"fmt"
"math/rand"
"time"
)
func shellSort(arr []int) {
n := len(arr)
gap := n / 2
for gap > 0 {
for i := gap; i < n; i++ {
temp := arr[i]
j := i
for j >= gap && arr[j-gap] > temp {
arr[j] = arr[j-gap]
j -= gap
}
arr[j] = temp
}
gap /= 2
}
}
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, 10000)
for i := range data {
data[i] = rand.Intn(1000)
}
shellData := make([]int, len(data))
copy(shellData, data)
start := time.Now()
shellSort(shellData)
shellTime := time.Since(start)
quickData := make([]int, len(data))
copy(quickData, data)
start = time.Now()
quickSort(quickData)
quickTime := time.Since(start)
fmt.Printf("Shell Sort time: %.6f seconds\n", shellTime.Seconds())
fmt.Printf("Quick Sort time: %.6f seconds\n", quickTime.Seconds())
}
此基准测试针对 10,000 个随机整数测试了这两种算法。Shell Sort 使用步长就地修改数组，而 Quick Sort 通过递归创建新切片。
由于其分治法的效率，Quick Sort 通常在大数据集上优于 Shell Sort。Shell Sort 在处理较小或部分排序的数据时表现出色，提供了实用的权衡。
理解这些差异有助于为 Go 中的特定用例选择最佳算法，平衡简洁性和速度。
来源
本教程介绍了 Go 中的 Shell Sort，包括数字和文本示例，以及与 Quick Sort 的性能比较。