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.
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(;
	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