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

This article mainly explains "what is Hill ranking". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what is Hill ranking".

Overview

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.

This conclusion is obvious that if most of the elements in an array are ordered, then the elements in the array naturally do not need to be compared and exchanged frequently.

In the case of a small number of elements, the workload of inserting sort is less.

This conclusion is more obvious that the workload of insertion sorting is proportional to the square of n, and if n is relatively small, then the workload of sorting is naturally much less.

That is to say: if we do some "preprocessing" to the data to make most of the elements of the original array orderly, then we use the insertion algorithm for sorting, then the efficiency of sorting will be greatly improved. Hill ranking is based on this line of thinking.

Take a chestnut.

This is the original array we have now:

In the first round, we take half of the total length, that is, 4, as the span, so that there are two groups, a total of four groups:

Next, we let each set of elements sort independently, sorting by inserting the sort directly. Because there are only two elements in each group, there is little effort to insert sorting. The array after each group is sorted is as follows:

In this way, the overall order of the array is significantly improved after only a few simple exchanges, which greatly reduces the workload of subsequent direct insertion sorting. This can be understood as a "rough adjustment" to the original array. But this is not over, we can further narrow the grouping span and repeat the above work. Reduce the span to half of the original span, that is, the span is 2, and regroup the elements into two groups:

Next, we continue to sort each set of elements independently, by directly inserting the sort. The array after each group is sorted is as follows:

Finally, we further reduce the packet span to 1, which is equivalent to doing direct insertion sorting. After a series of previous rough adjustments, the workload of directly inserting sorting is greatly reduced, and the sorting results are as follows:

Let's rearrange the whole process of grouping sorting:

Code implementation: public static int [] sort (int [] arr) {if (arr.length)

0; step / = 2) {for (int I = step; I

= step & & temp < arr [j-step]; j-= step) {/ / move back arr [j] = arr [j-step];} arr [j] = temp;}} return arr } Thank you for your reading. The above is the content of "what is Hill ranking". After the study of this article, I believe you have a deeper understanding of what Hill ranking is, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.