#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
# 稳定性：不稳定


def shell_sort(alist):
    n = len(alist)
    # 初始步长
    gap = round(n / 2)
    while gap > 0:
        for i in range(gap, n):
            # 每个步长进行插入排序
            temp = alist[i]
            j = i
            # 插入排序
            while j >= gap and alist[j - gap] > temp:
                alist[j] = alist[j - gap]
                j -= gap
            alist[j] = temp
        # 得到新的步长
        gap = round(gap / 2)
    return alist
