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 insert sort the group with a grouping increment of 2 until the grouping increment is 1
Code:
Python code
def shell_sort(lists):
#Hill sorting
count = len(lists) step = 2
group = count / step
while group > 0: # Increment grouping loop through group
for i in range(0, group) ;
. = 0: #Perform insertion sort in group group since