希尔排序（Shell Sort）是插入排序的一种改进版本，也称为缩小增量排序。它通过将待排序的列表分成若干子列表，对每个子列表进行插入排序，逐步缩小子列表的间隔，最终完成整
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。
1. 算法步骤
选择增量序列：选择一个增量序列（gap sequence），用于将列表分成若干子列表。常见的增量序列有希尔增量（
n/2, n/4, ..., 1）等。分组插入排序：按照增量序列将列表分成若干子列表，对每个子列表进行插入排序。
缩小增量：逐步缩小增量，重复上述分组和排序过程，直到增量为 1。
最终排序：当增量为 1 时，对整个列表进行一次插入排序，完成排序。
2. 动图演示
假设有一个待排序的列表 [8, 3, 1, 2, 7, 5, 6, 4]，使用希尔增量（初始增量为 n/2），排序过程如下：
初始状态：
列表：
[8, 3, 1, 2, 7, 5, 6, 4]。初始增量：
4（列表长度8的一半）。
第一轮（增量为 4）：
将列表分成 4 个子列表：
子列表 1：
[8, 7]。子列表 2：
[3, 5]。子列表 3：
[1, 6]。子列表 4：
[2, 4]。
对每个子列表进行插入排序：
子列表 1：
[7, 8]。子列表 2：
[3, 5]。子列表 3：
[1, 6]。子列表 4：
[2, 4]。
排序后的列表：
[7, 3, 1, 2, 8, 5, 6, 4]。
第二轮（增量为 2）：
将列表分成 2 个子列表：
子列表 1：
[7, 1, 8, 6]。子列表 2：
[3, 2, 5, 4]。
对每个子列表进行插入排序：
子列表 1：
[1, 6, 7, 8]。子列表 2：
[2, 3, 4, 5]。
排序后的列表：
[1, 2, 6, 3, 7, 4, 8, 5]。
第三轮（增量为 1）：
将整个列表视为一个子列表，进行插入排序。
排序后的列表：
[1, 2, 3, 4, 5, 6, 7, 8]。
实例
n = len(arr)
gap = n // 2 # 初始增量
while gap > 0:
# 对每个子列表进行插入排序
for i in range(gap, n):
temp = arr[i] # 当前待插入元素
j = i
# 在子列表中找到合适的位置插入
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2 # 缩小增量
return arr
# 示例
arr = [8, 3, 1, 2, 7, 5, 6, 4]
sorted_arr = shell_sort(arr)
print(sorted_arr) # 输出: [1, 2, 3, 4, 5, 6, 7, 8]
时间复杂度
希尔排序的时间复杂度取决于增量序列的选择：
最坏情况：O(n²)，当增量序列选择不当时。
最好情况：O(n log n)，当增量序列选择合适时。
平均情况：O(n log n) 到 O(n²) 之间。
常见的增量序列：
希尔增量：
n/2, n/4, ..., 1，时间复杂度为 O(n²)。Hibbard 增量：
1, 3, 7, 15, ..., 2^k - 1，时间复杂度为 O(n^(3/2))。Sedgewick 增量：
1, 5, 19, 41, 109, ...，时间复杂度为 O(n^(4/3))。
空间复杂度
O(1)，希尔排序是原地排序算法，不需要额外的存储空间。
优缺点
优点：
相对于简单插入排序，效率更高。
原地排序，不需要额外的存储空间。
适用于中等规模的数据集。
缺点：
时间复杂度依赖于增量序列的选择。
不稳定排序算法（可能改变相同元素的相对顺序）。
适用场景
中等规模的数据集。
对性能要求不高但需要比简单插入排序更高效的场景。
作为更复杂排序算法的预处理步骤。
代码实现
JavaScript
实例
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //动态定义间隔序列
gap =gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
Python
实例
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr
Go
实例
length := len(arr)
gap := 1
for gap < length/3 {
gap = gap*3 + 1
}
for gap > 0 {
for i := gap; i < length; i++ {
temp := arr[i]
j := i - gap
for j >= 0 && arr[j] > temp {
arr[j+gap] = arr[j]
j -= gap
}
arr[j+gap] = temp
}
gap = gap / 3
}
return arr
}
Java
实例
int length = arr.length;
int temp;
for (int step = length / 2; step >= 1; step /= 2) {
for (int i = step; i < length; i++) {
temp = arr[i];
int j = i - step;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
}
PHP
实例
{
$len = count($arr);
$temp = 0;
$gap = 1;
while($gap < $len / 3) {
$gap = $gap * 3 + 1;
}
for ($gap; $gap > 0; $gap = floor($gap / 3)) {
for ($i = $gap; $i < $len; $i++) {
$temp = $arr[$i];
for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
$arr[$j+$gap] = $arr[$j];
}
$arr[$j+$gap] = $temp;
}
}
return $arr;
}
C
实例
int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1)
for (i = gap; i < len; i++) {
temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}
C++
实例
void shell_sort(T array[], int length) {
int h = 1;
while (h < length / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
std::swap(array[j], array[j - h]);
}
}
h = h / 3;
}
}
参考地址：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/4.shellSort.md
https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
艾孜尔江
bju***ft@sina.com
我看这个没把 C# 版本写出来，我写了一下，下面是 C# 版本：
static void ShellSort(int[] arr) { int gap = 1; while (gap < arr.Length) { gap = gap * 3 + 1; } while (gap > 0) { for (int i = gap; i < arr.Length; i++) { int tmp = arr[i]; int j = i - gap; while (j >= 0 && arr[j] > tmp) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = tmp; } gap /= 3; } }艾孜尔江
bju***ft@sina.com
kezhuoquan
kez***quan@163.com
rust 版本：
fn shell_sort<T: Ord + Debug>(array: &mut [T]) { let mut grad = [1, 3, 5]; grad.reverse(); for step in grad { insert_sort_step(array, step) } } fn insert_sort_step<T: Ord + Debug>(array: &mut [T], step: usize) { for i in (0..array.len()).step_by(step) { for j in (0..i).step_by(step).rev() { if array[j + step] < array[j] { array.swap(j + step, j); } else { break; } } } }kezhuoquan
kez***quan@163.com