shell排序是插入排序（插入排序：https://blog.csdn.net/mars_xiaolei/article/details/77334970）的优化。 在待排序的元素数据量较大时，如果一个序列已经基本有序（序列中小数普遍位于大数的前面），那么我们在插入排序的时候，就可以在较少的比较操作之后使整体有序。shell排序会在插入排序操作之前尽量将待排数组变为基本有序的数组。 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<；…<d2<d1），即所有记录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。 原理图：
代码（来自：https://github.com/htliujy/TheAlgorithms/blob/master/sorts/shell_sort.py ）
"""
This is a pure python implementation of the shell sort algorithm
For doctests run following command:
python -m doctest -v shell_sort.py
or
python3 -m doctest -v shell_sort.py
For manual testing run:
python shell_sort.py
"""
from __future__
import print_function
def shell_sort(collection
):
"""Pure implementation of shell sort algorithm in Python
:param collection: Some mutable ordered collection with heterogeneous
comparable items inside
:return: the same collection ordered by ascending
>>> shell_sort([0, 5, 3, 2, 2])
[0, 2, 2, 3, 5]
>>> shell_sort([])
[]
>>> shell_sort([-2, -5, -45])
[-45, -5, -2]
"""
gaps
= [701, 301, 132, 57, 23, 10, 4, 1]
for gap
in gaps
:
i
= gap
while i
< len(collection
):
temp
= collection
[i
]
j
= i
while j
>= gap
and collection
[j
- gap
] > temp
:
collection
[j
] = collection
[j
- gap
]
j
-= gap
collection
[j
] = temp
i
+= 1
return collection
if __name__
== '__main__':
try:
raw_input
except NameError
:
raw_input = input
user_input
= raw_input('Enter numbers separated by a comma:\n').strip
()
unsorted
= [int(item
) for item
in user_input
.split
(',')]
print(shell_sort
(unsorted
))
原文：
https://www.cnblogs.com/oumyye/p/4199449.html https://blog.csdn.net/lemon_tree12138/article/details/51127533
