Hill sort (easy to understand, graphic and image, insert sort) Java code implementation

This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.

Hill sort is a more efficient and improved version of the direct insert sort algorithm.

Hill’s idea of ordering:

Group them according to increment D, and conduct direct insertion sort inside each group respectively; Generally, d is equal to half the length of the sequence, and then halved each time until the increment is equal to 1.

Here is the sorting process I drew with ProcessOn:

(Take 11 numbers as an example to illustrate, please carefully analyze this figure, be patient, write very detailed, read this figure should have a harvest) In the figure below, different colored lines represent different groups. For example, the first black line in the figure below is connected with 426, -2, 23, indicating that 426, -2, 23 are divided into a group, and 426, -2, 23 is directly inserted. The first blue line is 62 and 0, which means 62 and 0 are grouped together; The same is true for all of the following groups of connections.

Java implementation code (with comments) :

public void toShellSort(int []arr) {
	// Increments start at half the array length, and are halved each time until increments greater than 0 are invalid
	for(int d = (int)(arr.length/2); d > 0; d = (int)(d/2)) { 
		// Start with the second number in each group. The first loop compares the second number in the first group with the first number. The second loop compares the second number in the second group with the first number in the second group
		// After d loops, if there are more numbers
		// The DTH loop is the comparison of the third number in the first group with the previously ordered sequence. The d+1 loop is the comparison of the second and third numbers with the previously ordered sequence.
		// Sort each group separately
		for(inti = d; i<arr.length; i++) {int tempIndex = i;
			while(tempIndex - d >=0 && arr[tempIndex] < arr[tempIndex-d]) {  
				inttemp = arr[tempIndex]; arr[tempIndex] = arr[tempIndex-d]; arr[tempIndex-d] = temp; tempIndex = tempIndex-d; }}}}Copy the code

Operation effect screenshot:

The best time to plant a tree was 10 years ago. The next best time is now.