# encoding: utf-8
"""
 @project:data_structure_and_algorithm
 @author: Jiang Hui
 @language:Python 3.7.2 [GCC 7.3.0] :: Anaconda, Inc. on linux
 @time: 2019/4/22 23:10
 @desc:希尔排序，不稳定的算法，1959 年由D.L.Shell 提出来的，相对直接插入排序有较大的改进。希尔排序又叫缩小增量排序，也是插入排序算法的一种
"""
"""
 学习建议：阅读博客https://www.cnblogs.com/chengxiao/p/6104371.html，以图解的方式更容易理解希尔排序的流程
 
 1.基本思想
    希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，
    整个文件恰被分成一组，算法便终止。

 2.举例说明希尔排序的流程
    （1）假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过
        将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样(竖着的元素是步长组成)：
        13 14 94 33 82
        25 59 94 65 23
        45 27 73 25 39
        10
        
        每一列代表增量/gap为5的元素组成的子序列，然后对每一列进行直接插入排序，于是得到：
        10 14 73 25 23
        13 27 94 33 39
        25 59 94 65 82
        45
        
    （2）将上述四行数字，按行连接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]，以3为步长排序
        10 14 73 
        25 23 13
        27 94 33
        39 25 59
        94 65 82
        45
        
        每一列代表增量/gap为3的元素组成的子序列，然后对每一列进行直接插入排序，于是得到：
        10 14 13
        25 23 33
        27 25 59
        39 65 73
        45 94 82
        94
        
    （3）将上述六行数字，按行连接在一起时我们得到：[ 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 45 ]，以1为步长排序
        10
        14
        13
        25
        23
        33
        27
        25
        59
        39
        65
        73
        45
        94
        82
        45
        
        然后再对此列进行直接插入排序，此时的数列基本有序，只需要移动少数几个元素的位置即可，在原始的简单插入排序算法中进行了一定的优化
        
 3.时间复杂度分析
    希尔排序的时间复杂度与增量(即，步长gap)的选取有关。
    例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为O(n^2)，
    而Hibbard增量的希尔排序的时间复杂度为O(n^(3/2))。
"""


def shell_sort(nums):
    length = len(nums)
    gap = length // 2
    while gap >= 1:
        for j in range(gap, length):
            i = j
            while i - gap >= 0:
                if nums[i] < nums[i - gap]:
                    nums[i], nums[i - gap] = nums[i - gap], nums[i]  # python特有的交换两元素值的方式，不需要temp
                    i -= gap
                else:
                    break
        gap //= 2


if __name__ == '__main__':
    sort_nums = [13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10]
    print("origin_nums is ", sort_nums)
    shell_sort(sort_nums)  # 直接在原数组上进行修改
    print("sorted_nums is ", sort_nums)
