希尔排序（Shell Sort）是插入排序的改进版本，由Donald Shell于1959年提出。它通过将数组按特定间隔分成多个子序列，对每个子序列进行插入排序，逐步缩小间隔直至为1。这种方法使元素能够快速移动到大致正确的位置，从而提高排序效率。
1. **时间复杂度**：
- **最坏情况**：取决于间隔序列。原始序列（n/2, n/4,...）为O(n^2)，Hibbard序列为O(n^(3/2))，Sedgewick序列为O(n^(4/3))。
- **平均情况**：通常介于O(n log n)到O(n^2)之间，优化后的间隔序列（如Sedgewick）接近O(n log n)。
2. **空间复杂度**：
- O(1)，原地排序，仅需常数级额外空间。
---
### C++代码示例
```cpp
#include
using namespace std;
void shellSort(int arr[], int n) {
// 初始间隔为n/2，逐步缩小至1
for (int gap = n/2; gap > 0; gap /= 2) {
// 对每个子序列进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
int main() {
int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
shellSort(arr, n);
cout << "排序后数组：";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
**输出**：
```
排序后数组：1 2 3 4 5 6 7 8 9
```
---
### 适用场景
1. **中等规模数据**：比传统插入排序更高效，适合处理万级以下数据。
2. **内存敏感环境**：原地排序，无需额外内存。
3. **部分有序数据**：间隔排序能快速调整元素位置。
4. **非稳定性要求**：希尔排序不稳定，不适用于需稳定排序的场景。
**不适用场景**：
- 极大规模数据（优先选O(n log n)算法，如快速排序）。
- 严格要求稳定性的场景（如对象多关键字排序）。
---
### 优化方向
使用更高效的间隔序列（如Sedgewick序列）可进一步提升性能。例如，Sedgewick序列的生成公式为：
\[ 9 \times 4^i - 9 \times 2^i + 1 \] 或 \[ 2^{i+2} \times (2^{i+2} - 3) + 1 \]
可显著降低时间复杂度至O(n^(4/3))。