shell（希尔）排序算法

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]
    """
    # Marcin Ciura's gap sequence
    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          # Python 2
    except NameError:
        raw_input = input  # Python 3

    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