Code example of Python implementing Hill sorting

This article mainly introduces the implementation of Hill sorting in Python. The programmed Hill sorting has certain reference value. Interested friends can refer to it

Observe "insertion sort" : In fact, it is not difficult to find that she has a shortcoming:

If the data is "5, 4, 3, 2, 1", at this time we will insert the records in the "unordered block" into the "with" "Sequence block", it is estimated that we will crash, and the position will be moved every time we insert. At this time, the efficiency of insertion sort can be imagined.

Based on this weakness, the shell has improved the algorithm and incorporated an idea called "reducing incremental sorting method". It is actually quite simple, but something to note is:

Increment It's not random, but there are rules to follow.

Timeliness analysis of Hill sorting is difficult. The number of comparisons of key codes and the number of record moves depend on the selection of the increment factor sequence d, in certain circumstances The following can accurately estimate the number of key code comparisons and the number of recorded moves. No one has yet given a method for selecting the best incremental factor sequence. The sequence of incremental factors can be taken in various ways, including odd numbers and prime numbers. However, it should be noted that there are no common factors among the incremental factors except 1, and the last incremental factor must be 1. . Hill sorting method is an unstable sorting method. First of all, we need to clarify the method of increment (the pictures here are copied from other people's blogs, the increment is an odd number, and my programming below uses an even number):

The first increment The method of selecting is: d=count/2;

The method of selecting the second increment is: d=(count/2)/2;

Finally, it goes to: d=1;

Okay, pay attention to the picture. The increment d1=5 in the first pass divides the 10 records to be sorted into 5 subsequences,

performs direct insertion sorting respectively

, the result is (13, 27, 49, 55, 04, 49, 38, 65, 97, 76)The increment of the second pass is d2=3, and the 10 to-be-queued records are divided into 3 subsequences, and direct insertion is performed respectively. Sorting, the result is (13, 04, 49, 38, 27, 49, 55, 65, 97, 76)

The increment of the third pass is d3=1, direct insertion sorting is performed on the entire sequence,

The final result is (04, 13, 27, 38, 49, 49, 55, 65, 76, 97)Here comes the key point. When the increment decreases to 1, the sequence is basically in order.

The last pass of Hill sorting is direct insertion sorting

which is close to the best situation. The "macro" adjustments in the previous passes can be regarded as the preprocessing of the last pass, which is more efficient than doing only one direct insertion sort. I am learning python, and today I used python to implement Hill sorting.

def ShellInsetSort(array, len_array, dk): # 直接插入排序
 for i in range(dk, len_array): # 从下标为dk的数进行插入排序
 position = i
 current_val = array[position] # 要插入的数

 index = i
 j = int(index / dk) # index与dk的商
 index = index - j * dk

 # while True: # 找到第一个的下标，在增量为dk中，第一个的下标index必然 0<=index<dk
 # index = index - dk
 # if 0<=index and index <dk:
 # break

 # position>index,要插入的数的下标必须得大于第一个下标
 while position > index and current_val < array[position-dk]:
 array[position] = array[position-dk] # 往后移动
 position = position-dk
 else:
 array[position] = current_val

def ShellSort(array, len_array): # 希尔排序
 dk = int(len_array/2) # 增量
 while(dk >= 1):
 ShellInsetSort(array, len_array, dk)
 print(">>:",array)
 dk = int(dk/2)

if __name__ == "__main__":
 array = [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
 print(">:", array)
 ShellSort(array, len(array))

Output:

>: [49, 38, 65, 97, 76, 13, 27, 49, 55, 4]
>>: [13, 27, 49, 55, 4, 49, 38, 65, 97, 76]
>>: [4, 27, 13, 49, 38, 55, 49, 65, 97, 76]
>>: [4, 13, 27, 38, 49, 49, 55, 65, 76, 97]

First of all, you must know insertion sorting, otherwise you will definitely not understand it.

#Insertion sort is to insert and sort the numbers in the three yellow boxes in the picture above. For example: 13, 55, 38, 76

Look directly at 55, 55<13, without moving. Then look at 38, 38<55, then 55 is moved back, and the data becomes [13, 55, 55, 76]. Then compare 13<38, then 38 replaces 55 and becomes [13, 38, 55, 76]. The rest are the same, omitted.

There is a problem here, for example, the second yellow box

[27, 4, 65], 4<27, then 27 moves back, then 4 replaces the first one, and the data becomes [ 4, 27, 65],

But how does the computer know that 4 is the first one??My approach is to first

find the first one of [27, 4, 65] The subscript of a number. In this example, the subscript of 27 is 1

. When the subscript of the number to be inserted is greater than the first subscript 1, it can be moved backward. The previous number cannot be moved backward. There are two situations, one is If there is data in front and it is smaller than the number to be inserted, you can only insert it after it. Another, very important, when the number to be inserted is smaller than all the previous numbers, the inserted number must be placed first. At this time, the subscript of the number to be inserted = the subscript of the first number. (This passage may not be very understandable to beginners...)In order to find the subscript of the first number, the first thing I thought of was to use a loop, all the way to the front:

while True: # 找到第一个的下标，在增量为dk中，第一个的下标index必然 0<=index<dk
 index = index - dk
 if 0<=index and index <dk:
 break

When debugging, I found that using loops is a waste of time, especially when the increment d=1. In order to insert the last number in the list directly, I have to loop by 1 until the subscript of the first number. Later I learned Be smart, use the following method:

j = int(index / dk) # index与dk的商
index = index - j * dk

Time complexity:

The time complexity of Hill sorting is a function of the increment sequence taken, and it is difficult to analyze accurately. Some literature points out that when the incremental sequence is d[k]=2^(t-k+1), the time complexity of Hill sorting is

O(n^1.5),

where t is sorting Number of trips. Stability: Unstable

Hill sorting effect:

Reference materials: The programming is implemented by myself. It is recommended to Debug and take a look at the running process

Eight sorting algorithms in c++

Visually and intuitively experience several commonly used sorting algorithms

C#Seven classic sorting algorithm series (Part 2)

1. Non-systematic learning is also a waste of time. 2. Be a technical person who can appreciate beauty, understand art, and be good at art

The above is the detailed content of Code example of Python implementing Hill sorting. For more information, please follow other related articles on the PHP Chinese website!