【从零开始的算法指南】大概是代码注释最详细的希尔排序笔记
基本思想
将排序表分割成若干个字表L(i, i + d, i + 2d, ..., i + kd)对每个子表分别进行插入排序。下一趟分割将d减小，使得部分有序的子表变大。当d = 1时，排序表全表有序。d通常被成为步长，d可以根据具体情况进行取值，不过一般情况第一趟一般取表长的一半。
算法代码
void
sort_shell
(
vector
<
int
>
&
A
,
int
n
)
{
//传入排序表和表长 n = A.size()
for
(
int
d
=
n
/
2
;
d
>=
1
;
d
=
d
/
2
)
//设置每趟排序的步长
{
for
(
int
i
=
1
+
d
;
i
<=
n
;
++
i
)
{
//一趟排序
if
(
A
[
i
]
<
A
[
i
-
d
]
)
{
//将A[i]插入有序部分
A
[
0
]
=
A
[
i
]
;
//暂存在A[0]
for
(
int
j
=
i
-
d
;
j
>
0
&&
A
[
0
]
<
A
[
j
]
;
j
-=
d
)
{
//找到插入位置
A
[
j
+
d
]
=
A
[
j
]
;
}
A
[
j
+
d
]
=
A
[
0
]
;
//完成插入操作
}
}
}
}
时间复杂度：希尔排序的时间复杂度依赖于步长序列的函数，计算比较困难，约为O(N^1.3)，最坏情况下仍为O(N^2)
空间复杂度：O（1）只需要常数个单位，暂存比较元素
稳定性：不稳定，如果相同关键字的元素没有被分到同一个子表，那么他们相对的先后次序就可能会改变
觉得文章不错有所帮助的话，记得帮我点个赞，也可以关注下我！