希尔排序（Shell Sort）
希尔排序是插入排序的改进版，1959 年由 Donald Shell 提出：按增量把数组分成若干组分别做插入排序，再逐步缩小增量。最坏时间复杂度 $O(n^2)$，但实践中通常比简单插入排序快得多。
1. 希尔排序的基本概念
希尔排序的基本思想是：
- 选择增量序列（Gap Sequence）: 选择一个增量序列，该序列用于将数组分成若干个子数组，每个子数组的元素间隔为增量值。
- 分组插入排序: 对每个增量值对应的子数组执行插入排序。通过增量值逐步减小，逐渐使整个数组变得接近排序状态。
- 逐步缩小增量: 按照增量序列中的增量值逐步缩小增量，直到增量为 1 时，执行一次完整的插入排序。
2. 希尔排序的算法步骤
选择增量序列: 例如 1, 4, 13, 40, 121。这些增量序列通常遵循某种数学规律，常见的有希尔增量序列和 Hibbard 增量序列。
分组插入排序: 对每个增量值，把下标相差该值的元素分成一组，对每组执行插入排序。
逐步缩小增量: 增量按序列逐步减小，减到 1 时做一次完整插入排序，完成。
3. 希尔排序的时间复杂度和空间复杂度
时间复杂度:
- 最坏情况: $O(n^2)$，具体复杂度取决于增量序列的选择。
- 最佳情况: $O(n \log n)$，对于某些特定的增量序列，希尔排序可以实现接近 $O(n \log n)$ 的时间复杂度。
- 平均情况: $O(n \log^2 n)$，具体复杂度取决于增量序列的选择和输入数据的分布。
空间复杂度:
- 空间复杂度: $O(1)$，希尔排序是原地排序算法，不需要额外的存储空间来存储排序结果。
4. 希尔排序的代码示例
go
package main
import "fmt"
// ShellSort 对整数切片进行希尔排序
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() {
arr := []int{64, 34, 25, 12, 22, 11, 90}
fmt.Println("Original array:", arr)
ShellSort(arr)
fmt.Println("Sorted array:", arr)
}5. 希尔排序的优缺点
优点:
- 比插入排序快: 相比简单插入排序，希尔排序在实践中更快，对中等规模的数据尤其明显。
- 原地排序: 不需要额外的存储空间，也不需要复杂的数据结构。
缺点:
- 复杂的时间复杂度: 希尔排序的时间复杂度依赖于增量序列的选择，最坏情况下的复杂度为 $O(n^2)$。
- 不稳定排序: 希尔排序不是稳定的排序算法，相同值的元素可能会改变相对位置。
总结
希尔排序原地完成，代码就是外层缩小增量、内层按步长做插入排序的三层循环。最坏 $O(n^2)$，平均约 $O(n \log^2 n)$，都取决于增量序列的选择；它不稳定，相同值的元素可能改变相对位置。