Shell Sort

The content of this paper comes from Data structure Textbook (C Language version )
Shell Sort (Shell’s Sort), Also known as reducing incremental sorting (Diminishing Increment Sort), It is also a method of insertion sort , But in terms of time efficiency, it is much better than the previous insertion sorting .

its The basic idea yes ： First, divide the whole record sequence to be sorted into several subsequences , separately , Direct insert sort , When the records in the whole sequence are basically in order , Do a direct insertion sort for all records again .

The above picture description is too ambiguous , Hard to understand , The detailed decomposition diagram is as follows ：

Sort using increment ( Stepping ) One time for 5, 3, 1, The first round of use 5 For stepping , From the subscript 0 Start backward with the subscript (0+5) Compare the numbers at , Small numbers go forward ( left ), Big numbers go backwards ( On the right side ), Then the subscript is 1 Start , by 2 Start , Step backward in turn until there is no step for 5 The second number of , Then the first round of sorting is completed .
Let's take the first round as an example to analyze in detail ：

• First step
  
• The second step
  
• The third step
  
• Step four
  
• Step five
  
  The above is the detailed process of the first round of sorting , The second round , The third round just changed the step , The basic idea has not changed .

Hill sort algorithm uses Java The implementation is as follows

	/** *  Specific sorting process  * @param arr * @param dk  The incremental  */
	void shellInsert(int[] arr, int dk) {
    
		//  An array arr Make a hill insertion sort .
		for (int i = dk; i < arr.length; i++) {
    
			if (arr[i] <= arr[i - dk]) {
    
				int temp = arr[i];

				int j = 0;
				for (j = i - dk; j >= 0 && temp <= arr[j]; j -= dk) {
    
					arr[j + dk] = arr[j];
				}
				arr[j + dk] = temp;
			}

		}
	}// Shell Insert
	
	void ShellSort(int[] arr, int[] dlta, int t) {
    
		//  Sequence by increment dlta[0..t-1] For the sequence table arr Make Hill sort 
		for (int i = 0; i < t; i++) {
    
			shellInsert(arr, dlta[i]);
		}
	}
	
	@Test
	public void fun1() {
    
		int[] arr = {
     49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };
		int[] dlta = {
     5, 3, 1 };
		ShellSort(arr, dlta, dlta.length);

		System.out.println(Arrays.toString(arr));
	}

The analysis of Hill sort is a complex problem , Because its time is a function of the sequence quantity taken , This involves some unsolved mathematical problems .( The printing time of the textbook 2009 year 2 month , The time of publication is 2007 year , This year, 2019 year , It's about past publication 12 year , I wonder if these mathematical problems have been solved over the years .) The rest is like ： Local conclusions drawn from a large number of studies , Taking incremental sequence , Let's read the textbook , There's a lot of content .