希尔排序（Shell Sort）

本实验实现希尔排序算法，完成对整型数组的升序排序。

希尔排序是插入排序的一种改进版本，也称为"缩小增量排序"。它通过将原始数组按一定间隔（增量）分组，对每组使用插入排序进行预排序，随着增量逐渐减小，整个数组越来越接近有序，当增量减至 1 时，相当于对几乎有序的数组进行一次插入排序。

算法概述

希尔排序的核心思想是突破插入排序只能交换相邻元素的局限，允许远距离元素的交换，从而加快排序速度。

• 基于插入排序改进，使用分组插入策略
• 初始增量为数组长度一半，逐步减半
• 对整型数组进行原地升序排序
• 时间复杂度：优于 $O(n^2)$，平均 $O(n\log n)$
• 空间复杂度：$O(1)$

Baseline 任务：希尔排序的实现

任务内容

完成 ShellSort.cpp，实现希尔排序：

• 基于插入排序改进，使用分组插入策略
• 初始增量为数组长度一半，逐步减半
• 对整型数组进行原地升序排序
• 时间复杂度：优于 $O(n^2)$，平均 $O(n\log n)$
• 空间复杂度：$O(1)$

验证方式

• 编译：g++ testShellSort.cpp ShellSort.cpp -o testShellSort
• 运行：./testShellSort

文件结构

• ShellSort.h：希尔排序函数声明
• ShellSort.cpp：希尔排序核心算法实现
• testShellSort.cpp：测试程序，验证排序功能正确性