§07 排序算法
希尔排序
按递减增量分组做插入排序：先让相隔较远的元素有序，再逐步缩小增量，最后一轮 gap=1 收尾。 平均 O(n^1.3)，不稳定。观察 pivot 元素如何在组内跳跃插入。
希尔排序
伪代码
1
procedure shellSort(a, n)
2
gap = n / 2
3
while gap > 0 do
4
for i = gap to n - 1 do
5
temp = a[i]
6
j = i
7
while j >= gap and a[j - gap] > temp do
8
a[j] = a[j - gap]
9
j = j - gap
10
end while
11
a[j] = temp
12
end for
13
gap = gap / 2
14
end while
15
end procedure