C# 实现希尔排序算法：原理、代码与性能解析

Ryan

发布时间：2026-10-16| 6人浏览过

原创

希尔排序是插入排序的高效改进版，通过交换不相邻元素对数组进行局部排序，最终利用插入排序处理全局有序数组。本文将深入解析其核心思想，提供 C# 完整代码实现，并结合实际测试数据分析其性能优势。

结果或目标

希尔排序旨在解决大规模乱序数组中插入排序效率低下的问题。由于插入排序仅能交换相邻元素，导致元素移动速度极慢（每次仅移动一位）。希尔排序通过允许较远距离的元素交换，快速将大元素移至后端、小元素移至前端，从而大幅减少倒置次数，最终在 h=1 时利用插入排序完成收尾，实现整体高效排序。

准备条件

开发环境：支持 C# 的 IDE（如 Visual Studio 或 VS Code）。
基础库：System.Diagnostics（用于 Stopwatch 计时）和 System.Collections.Generic（用于 IComparable 接口）。
逻辑理解：需理解“h-有序”概念，即任意间隔为 h 的元素组成的子序列都是有序的。

真实操作顺序

第 1 步：理解希尔排序的核心增量选择策略

希尔排序的关键在于增量序列 h 的选择。常见的策略是从较小的 h 开始逐渐增大，直到超过数组长度，然后反向递减至 1。代码中采用 h = h * 3 + 1 的递增规则，这是一种经验证的较好序列：

初始化 h：从 1 开始，不断执行 h = h * 3 + 1，直到 h >= n / 3（n 为数组长度）。
递减循环：当 h 大于等于 1 时，执行内层排序逻辑。
缩小增量：每轮结束后，h = h / 3，直至 h=1 结束。

如图所示，随着 h 值的减小，排序范围逐渐从粗粒度跳跃变为细粒度的局部调整，最终过渡到标准的插入排序。

第 2 步：编写 C# 代码实现 ShellSort 类

以下是基于 IComparable 接口的通用希尔排序实现。代码中包含详细的注释说明每一步的目的：

public class Shell : BaseSort
{
    public static long usedTimes = 0;

    public Shell()
    {
    }

    public static void Sort(IComparable[] a)
    {
        // 1. 开启计时器以评估性能
        Stopwatch timer = new Stopwatch();
        timer.Start();

        int n = a.Length;
        int h = 1;

        // 2. 计算初始 h 值 (h = h * 3 + 1)，确保 h 接近 n/3
        while (h < n / 3)
            h = h * 3 + 1;

        // 3. 主循环：从大到小递减 h
        while (h >= 1)
        {
            // 4. 对每个间隔为 h 的子序列进行插入排序
            for (int i = h; i < n; i++)
            {
                // 5. 向前比较并交换：如果当前元素小于间隔 h 前的元素，则交换
                // j >= h 保证不越界，Less(a[j], a[j - h]) 判断是否需要交换
                for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
                {
                    Exch(a, j, j - h);
                }
            }
            // 6. 缩小增量 h
            h = h / 3;
        }

        timer.Stop();
        usedTimes = timer.ElapsedMilliseconds;
    }
}

关键逻辑解析：