Shulou(Shulou.com)06/01 Report--

Editor to share with you how to achieve Hill sorting in web development, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's learn about it!

Hill ranking

Hill sorting, also known as decreasing incremental sorting algorithm, is a more efficient and improved version of insert sorting. But Hill sorting is an unstable sorting algorithm.

Hill sorting is an improved method based on the following two properties of insertion sorting:

Insertion sorting is efficient when operating on almost sorted data, that is, it can achieve the efficiency of linear sorting.

But insert sorting is generally inefficient because it can only move data one bit at a time.

The basic idea of Hill sorting is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion and sorting, and then all the records are directly inserted and sorted when the records in the whole sequence are "basically ordered".

Algorithm step

Select an incremental sequence T1 and T2,. , tk, where ti > tj, tk = 1

Sort the sequence k times according to the number of incremental sequences k

In each sorting, according to the corresponding incremental ti, the sequence to be arranged is divided into several subsequences of length m, and each subtable is sorted directly. Only when the increment factor is 1, the whole sequence is treated as a table, and the table length is the length of the whole sequence.

Source: https://github.com/hustcc/JS-Sorting-Algorithm

Algorithm demonstration

Process interpretation of sorting animation

First of all, select the increment gap = 10 gap/2 2, reduce the increment and continue in the form of gap = gap/2

The initial increment is gap = 10 impulse 2 = 5, and the whole array is divided into five groups.

Divided by color into [8,3], [9,5], [1,4], [7,6], [2,0]

Use the insertion sort described in the previous section for these five separate groups

As a result, it can be found that the relatively small elements in these five groups have been adjusted to the front.

Zoom out the increment gap = 5 stroke 2 = 2, and the whole array is divided into two groups

[3, 1, 0, 9, 7], [5, 6, 8, 4, 2]

Use the insertion sort described in the previous section for these two separate groups

At this point, the ordering of the whole array is very obvious.

Then reduce the increment gap = 2 stroke 2 = 1, and the whole array is divided into 1 group.

[0, 2, 1, 4, 3, 5, 7, 6, 9, 0]

At this point, you only need to make simple fine-tuning to the above array, and you don't need a lot of moving operations to complete the sorting of the whole array.

Code implementation

In order to better let readers use their familiar programming language to understand animation, the author will post the reference code of a variety of programming languages, all from the Internet.

C++ code implementation

Java code implementation

Python code implementation

JavaScript code implementation

The above is all the contents of the article "how to achieve Hill sorting in web Development". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.