Shulou(Shulou.com)05/31 Report--

This article mainly explains "how C++ achieves Hill ranking". The content in the article is simple, clear and easy to learn and understand. Please follow the editor's train of thought. Let's study and learn "how C++ achieves Hill ranking".

Initially, there is an unordered sequence of size 10.

In the first sort, we might as well set gap1 = N / 2 = 5, that is, elements with a distance of 5 form a group, which can be divided into five groups.

Next, sort each group by inserting the sort directly.

In the second sort, we cut the last gap by half, that is, gap2 = gap1 / 2 = 2 (take an integer). In this way, elements with a distance of 2 are grouped together and can be divided into two groups.

Sort each group according to the method of directly inserting sort.

In the third sort, reduce the gap by half again, that is, gap3 = gap2 / 2 = 1. In this way, elements with a distance of 1 form a group, that is, there is only one group.

Sort each group according to the method of directly inserting sort. At this point, the sorting is over.

It should be noted that there are two elements 5 and 5 with equal values in the figure. We can clearly see that during the sorting process, the positions of the two elements are exchanged.

Therefore, Hill sorting is an unstable algorithm.

Package com.lifeibigdata.fight;/** * Created by lifei on 16-10-24. * / public class ShellSort {static int [] shellSort (int [] a) {int gap = a.length / 2; while (gap > = 1) {/ / organize elements with distance of gap into a group and scan all groups / / for (int I = gap; I)

= 0 & & temp < a [j]; j = j-gap) {/ / TODO j-gap// a [j + gap] = a [j]; / / TODO I-gap + gap//} / / a [j + gap] = temp;//TODO j-gap + gap = jamp /} for (int I = gap; I < a.length If +) {if (a [I] < a [I-gap]) {/ / 20; 3 1 42; int tmp = a [I]; a [I] = a [I-gap]; a [I-gap] = tmp;}} gap = gap / 2 } return a;} public static void main (String [] args) {int [] a = new int [] {9, 1, 2, 5, 7, 4, 8, 6, 3, 5}; int [] r = shellSort (a); for (int XRU r) {System.out.println (x);}

Comparison between direct insertion sort and Hill sort

The direct insertion sort is stable; the Hill sort is unstable.

Direct insertion sorting is more suitable for collections where the original records are basically ordered.

The number of comparisons and movements of Hill sort is less than that of direct insertion sort, and the greater the N, the more obvious the effect.

In Hill sorting, the selection of incremental sequence gap must satisfy: the last step must be 1.

Direct insertion sorting also applies to chained storage structures; Hill sorting does not apply to chained structures.

Thank you for your reading. the above is the content of "how to achieve Hill ranking on C++". After the study of this article, I believe you have a deeper understanding of how to achieve Hill ranking on C++. The specific use also 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.