Hill's idea of sequencing
Hill sort is an improved method of insertion sort , It divides the original list into countless sub lists , Then insert sort is performed on each sub list , The key to Hill sorting is to control the step size （ It can be seen as taking elements as sub lists every few elements ）.
Graphic Hill sort
Given the following list ：
We use 2 As step size （ Take an element every two characters ）, It can be divided into three sub lists as follows .
With three sub lists , We insert and sort the three sub lists respectively
According to the above figure, we can find that the combination results we obtained are not completely sorted successfully , Finally, we need to do an insert sort on the list .
So our Hill sorting is complete .
The nature of Hill sort
- Optimal time complexity ： O ( n ) O(n) O(n)
- Worst time complexity ： O ( n 2 ) O(n^2) O(n2)
- stability ： unstable
- Compare insert sort ： By changing the increment, the time complexity will be optimized .
Hill sort code implementation
lst = list(map(int, input().split(','))) def shell_sort(alist): n = len(alist) gap = n // 2 while gap > 0: for i in range(gap, n): j = i while j >= gap: if alist[j] < alist[j - gap]: alist[j], alist[j - gap] = alist[j - gap], alist[j] j -= gap else: break gap //= 2 return alist shell_sort(lst)