# Java eight sorting -- Hill sorting

Problems with direct insertion sorting:
When the number of insertions behind is small, the number of backward shifts of the elements arranged in front will increase significantly, which has an impact on efficiency.
Sorting:
Improvement on the basis of direct insertion sort is also called reduced incremental sort.
Basic ideas:
Hill sorting is grouping the records according to a certain increment of the subscript, sorting each group by using the direct insertion sort algorithm; with the increment decreasing, each group contains more and more keywords, and when the increment is reduced to 1, the whole element set is divided into a set, and the algorithm terminates.

Dynamic diagrams: Java code implementation:

```import java.util.Scanner;

public class Shell_sort {

//Sorting is an unstable sorting algorithm.

//Basic ideas:
//First, take an integer d1 less than n as the first increment, and group all the data. All records with multiple distances of d1 are placed in the same group. Firstly, insert and sort directly in each group.
//Then, take the second increment D2 < D1 to repeat the above grouping and sorting. Until the increment d=1, i.e., all records are placed in the same group for direct insertion sort
//Generally, half of the initial sequence is incremental, and then halves each time until the increment is 1.

public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Enter the size of the array:");
Scanner input = new Scanner(System.in);
int a = input.nextInt();
int [] arr = new int[a];
for(int i = 0;i<arr.length;i++) {
System.out.println("Please enter the number of arrays"+i+"Value:");
int s = input.nextInt();
arr[i] = s;
}
arr = HillSort(arr);
for(int i = 0;i<arr.length;i++)
System.out.print(" "+arr[i]+" ");
}
public static int[] HillSort(int[] arr) {
//Take out the length of the array separately to improve efficiency
int length = arr.length;
//If the intercepted length is not 1, it will be calculated all the time.
while(length!=0) {
//Integration, equal to the number of elements in each group
length = length/2;
//The number of elements in each group is repeated several times.
for(int i =0;i<length;i++) {
int tem = arr[i];
//Grouping elements
for(int j = i+length;j<arr.length;j+=length) {
//The value of k is an array subscript for the last value of each group.
int k = j-length;
//Assign each number to be inserted to an intermediate variable
int temp = arr[j];
//Compare this number, and if it is smaller than the ordered array, the array moves backwards.
while(k>=0&&temp<arr[k]) {
//Corresponding Elements Move Back
arr[k+length] = arr[k];
//Corresponding subscript forward
k-= length;
}
//Find the location of elements not less than the ordered array and insert them
arr[k+length] = temp;
}
}
}
return arr;

}
}
```

Keywords: Java less

Added by lance1208 on Tue, 01 Oct 2019 16:48:05 +0300