希尔排序思想：
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
def
shell_sort
(
list
)
:
n
=
len
(
list
)
gap
=
n
//
2
new_list
=
[
]
while
gap
>
1
:
for
i
in
range
(
gap
)
:
if
list
[
i
]
>
list
[
i
+
gap
]
:
list
[
i
]
,
list
[
i
+
gap
]
=
list
[
i
+
gap
]
,
list
[
i
]
gap
=
gap
//
2
;
if
gap
==
1
:
for
j
in
range
(
n
)
:
if
j
==
0
:
new_list
.
append
(
list
[
j
]
)
else
:
new_list
.
append
(
list
[
j
]
)
for
k
in
range
(
j
,
0
,
-
1
)
:
if
new_list
[
k
]
<
new_list
[
k
-
1
]
:
new_list
[
k
]
,
new_list
[
k
-
1
]
=
new_list
[
k
-
1
]
,
new_list
[
k
]
return
new_list
if
__name__
==
'__main__'
:
a
=
[
58
,
89
,
56
,
3
,
4
,
5
,
79879
,
263536
,
45215
,
4543
]
b
=
shell_sort
(
a
)
print
(
b
)
