Go语言希尔排序算法原理与代码实现详解

阿橙

发布时间：2026-10-15| 5人浏览过

原创

介绍Go语言中希尔排序算法的实现细节，包括其核心思想、通过缩小增量分组进行的排序过程图解，以及包含空间O(1)与稳定性说明的代码示例。

希尔排序的核心逻辑

希尔排序（Shell Sort），又称“缩小增量排序”，是由 Donald Shell 于 1959 年提出的高效排序算法。它基于直接插入排序，通过两个维度的改进显著提升效率：

减少记录个数：将待排序序列按下标的一定增量进行分组，使得每次排序处理的元素数量减少。
基本有序：对每组使用直接插入排序，随着增量逐渐减小，整个序列会越来越接近有序状态。

当增量减至 1 时，整个序列已基本有序，此时进行一次直接插入排序即可完成最终排序。这种策略有效避免了直接插入排序中较小值从右端移到左端时需要的大量移动操作。

算法执行步骤

假设待排序数组为 array[0...n-1]，增量序列为 {g1, g2, ..., gt}，其中 n > g1 > g2 > ... > gt = 1。具体操作顺序如下：

第一趟：设定初始增量 g1，将所有间距为 g1 的记录分为一组，分别在各组内进行插入排序。
后续趟次：依次减小增量（如 g2, g3...），重复分组与组内插入排序的过程。
最后一趟：当增量 gt = 1 时，所有记录被视为一组，进行最后一次直接插入排序，确保整体有序。

图解算法演示

以数组 [7, 4, 3, 5, 2, 1, 6] 为例，演示希尔排序的具体变化过程：

第一步：增量设置为 3

将数组按间隔 3 分组：(7, 5), (4, 2), (3, 6), (5)。对各组内部进行排序调整后，数组状态发生变化。此步骤让相距较远的元素提前交换到正确的大致位置。

第二步：增量缩小为 2

当前数组继续按间隔 2 分组。例如原索引 0 和 2 的元素归为一组，1 和 3 归为一组等。通过更细致的组间插入排序，进一步消除逆序对。

第三步：增量缩减为 1

此时所有元素处于同一组，执行标准的直接插入排序。由于之前的多轮处理，此时数组已近乎有序，仅需极少的比较和移动即可完成排序。

Go 语言代码实现

在 Go 中实现希尔排序，关键在于控制外层循环的 gap（增量）变化，并在内层实现针对每组的插入逻辑。以下是完整实现：

package main

import "fmt"

// swap 交换切片中两个位置的元素
func swap(array []int, a int, b int) {
    array[a] = array[a] + array[b]
    array[b] = array[a] - array[b]
    array[a] = array[a] - array[b]
}

// shellSort 希尔排序主函数
func shellSort(array []int, length int) {
    // 初始增量为长度的一半，每次减半直到为1
    for gap := length / 2; gap > 0; gap = gap / 2 {
        // 从 gap 开始遍历，对每个元素进行组内插入排序
        for i := gap; i < length; i++ {
            var j = i
            // 在当前组内向前查找合适位置
            for {
                if j-gap < 0 || array[j] >= array[j-gap] {
                    break
                }
                swap(array, j, j-gap)
                j = j - gap
            }
        }
    }
}

func main() {
    nums := []int{7, 4, 3, 5, 2, 1, 6}
    length := len(nums)
    shellSort(nums, length)
    
    fmt.Println("排序结果:")
    for _, num := range nums {
        fmt.Printf("%d\n", num)
    }
}

运行上述代码的输出结果如下：