Use python to implement 8 major sorting algorithms-Hill sorting

The basic idea of ​​​​Hill sorting:

Hill sorting is an improvement based on insertion sorting. Since insertion sorting is efficient when operating on arranged arrays, insertion sorting is generally inefficient because it can only be moved at a time. One person. So Hill sort sorts by grouping first until the grouping increment is 1.

Example:

arr = [49,38,04,97,76,13,27,49,55,65], when the grouping increment is 5, the red numbers are in one group, insertion sorting is performed, and the loop is traversed in sequence

arr = [13,38,04,97,76,49,27,49,55,65], after the traversal is completed, the grouping increment decreases,

arr = [13,27,04,55,65 ,49,38,49,97,76], and then continue to perform insertion sorting on the group with a grouping increment of 2 until the grouping increment is 1

Code:

Python code

def shell_sort(lists):  
    #希尔排序  
    count = len(lists)  
    step = 2  
    group = count / step  
    while group > 0:  #通过group增量分组循环  
        for i in range(0, group):  
            j = i + group  
            while j < count:  #分组中key值的索引，通过增量自增  
                k = j - group  
                key = lists[j]  
                while k >= 0:  #分组中进行插入排序  
                    if lists[k] > key:  
                        lists[k + group], lists[k] = lists[k], key  
                    else: break  
                    k -= group  
                j += group  
        group /= step  
    return lists