How to implement Java Hill sorting
This article mainly explains "how to achieve Java Hill sorting". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to achieve Java Hill sorting".
Hill sort (shell sort) is a kind of insert sort, which is a more efficient algorithm after the improvement of simple insert sort, which is also called reduced incremental sort.
An introduction to Hill's sorting thought
To put it simply, Hill sorting is to logically divide a larger data set into several smaller sets, and then insert and sort each group separately.
For example, suppose there are n elements in the sequence of elements to be sorted. First, an integer increment (less than n) is taken as the interval to divide all elements into increment subsequences, and direct insertion sorting is performed in each subsequence. Then narrow the interval increment and repeat the above subsequence division and sorting work. Until the increment=1 is finally taken and all the elements are sorted in the same subsequence.
Algorithm description:
Data to be sorted: 12, 1, 6, 7, 4, 10, 5, 9
The first increment is the length of the array element / 2, that is, increment=4, resulting in four groups:
Group 1: 12, 4
Group 2: 1, 10
Group 3: 6, 5
Group 4: 7, 9
Insert and sort the four groups respectively, and finally get:
4,1,5,7,12,10,6,9
In the second comparison, increment takes half of the previous value, that is, increment=2, and gets two groups:
Group one: 4, 5, 12, 6
Group 2: 1, 7, 10, 9
Insert and sort the two groups respectively, and finally get:
4, 1, 5,7, 6,9,12,10
The third comparison, increment=1, that is, there is only one group:
Group 1: 4, 1, 5, 5, 7, 6, 9, 12, 10
Insert and sort it, and finally get:
1,4,5,6,7,9,10,12
Code implementation of Hill sorting
1. Public static void shellSort (int [] arr) {
2. Int temp = 0
3. Int j = 0
4. / / the initial value of the increment is half of the length, and the increment becomes half of the original each time.
5. For (int inc = arr.length/2; inc > = 1; inc / = 2) {
6. For (int I = inc; I
< arr.length; i++){ 7. temp = arr; 8. //将当前数与减去增量之后位置的数进行比较，如果大于，则后移 9. for(j = i - inc; j >= 0; j-= inc) {
10. If (arr [j] > temp) {
11. Arr [j + inc] = arr [j]
12.} else {
13. Break
14.}
15.}
16. Arr [j + inc] = temp
17.}
18.}
19.}
Thank you for your reading, the above is the content of "how to achieve Java Hill sorting". After the study of this article, I believe you have a deeper understanding of how to achieve Java Hill sorting, 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!
