This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Algorithm idea

The first set of numbers to be sorted is divided into groups at some increment D (n/2, where n is the number of numbers to be sorted), and the subscripts recorded in each group differ d. Direct insert sort is done for all elements in each group, and then it is grouped by a smaller increment (D /2), and direct insert sort is done again in each group. When the increment is reduced to 1, the sort is complete after direct insert sort.

Sorting process:

To be sorted: 39,80,76,41,13,29,50,78,30,11,100,7,41,86

Step d is 5,3,1

D =5 39,80,76,41,13,29,50,78,30,11,100,7,41,86

            |——————————-|—————————–|

                    |——————————|——————————|

                            |—————————–|——————————|

                                     |—————————-|——————————|

                                              |——————————-|

Their sequences are: {39,29,100} {80,50,7} {76,78,41} {41,30,86} {13,11}

Direct insertion sort is carried out for each self-sequence, and the sequence is called into the corresponding sorting elements of each self-sequence, and the first sorting result is obtained:

D =3 29,7,41,30,11,39,50,76,41,13,100,80,78,86

             |—————–|—————–|—————–|——————|

                     |—————-|——————|—————–|——————|

                            |——————|—————–|——————-|

Their sequences are: {29,30,50,13,78} {7,11,76,100,86} {41,39,41,80}. Direct insertion sort is carried out for each self-sequence, and the sequence is called into the corresponding sorting elements of each self-sequence, and the second sorting result is obtained:

D =1 13,7,39,29,11,41,30,76,41,50,86,80,78,100

At this point, the sequence is basically “ordered”, and the final result is obtained by directly inserting and ordering it:

7，11，13，29，30，39，41，41，50，76，78，80，86，100  

2. Algorithm code

import java.util.Arrays;
 
/** * Hill sort: insert sort directly with step size *@author xcbeyond
 * @date2012-7-8 11:27:32 */
public class ShellSort {
	public static void main(String[] args) {
		int a[] ={13.15.37.89.60.39.12.109.56.72}; shellSort(a); System.out.println(Arrays.toString(a)); }public static void shellSort(int[] array){
		int temp; 
		int d =array.length;/ / step length
		while(true){ 
			d= d/2; 
		
			for(int i=0; i<d; i++){for(intj=i+d; j<array.length; j+=d){int k=j-d; 
					temp=array[j]; 
					for(; k>=0&&temp<array[k];k-=d){ 
						array[k+d]=array[k]; 
					} 
					array[k+d]=temp; 
				} 
			} 
		if(d==1) 
			break; }}}Copy the code