Hill sorting performs well for medium-sized array sorting of up to several thousand data items. Hill sorting is not as fast as quick sort and other sorting algorithms with a time complexity of O(n*logn). Therefore, it is suitable for It is not the optimal choice for sorting very large files, but Hill sorting is much faster than selection sorting and insertion sorting, which have a time complexity of O(n²), and it is very easy to implement and the code is short.
Hill sorting is also a kind of insertion sort. In insertion sort, if the smallest number is at the end, there are too many copies. Hill solves this problem. It is also n-incremental sorting. Its idea is By increasing the spacing between elements in insertion sorting, and performing insertion sorting among these spacing elements, when these data items are sorted once, the Hill sorting algorithm reduces the spacing between data items and then sorts them, and so on. Go down. The spacing between data items when performing these sorts is called an increment, and is conventionally represented by the letter h.
For an array that is about to be sorted by Hill, the starting interval should be larger, and then the interval should be continuously reduced until the interval becomes 1.
Spacer sequence:
The quality of numbers in spaced sequences is often considered important - they have no common divisors other than 1. This constraint makes it more likely that each sorting pass will preserve the effect of the previous pass. For different spaced sequences, there is a The absolute condition is that the gradually decreasing interval must finally equal 1. Therefore, the last pass is an ordinary insertion sort.
The examples listed below are derived from the rule h=h*3+1:
package com.jll.sort; public class ShellSort { int[] arr; int size; public ShellSort() { super(); } public ShellSort(int size) { this.size = size; arr = new int[size]; } /** * @param args */ public static void main(String[] args) { ShellSort ss = new ShellSort(10); for(int i=0;i<10;i++){ ss.arr[i] = (int) ((Math.random()*100)+1); System.out.print(ss.arr[i]+" " ); } ss.shellSort(); System.out.println(); System.out.println("after sort:"); for(int i=0;i<10;i++){ System.out.print(ss.arr[i]+" "); } } public void shellSort(){ int h = 1; while(h<=size/3){ h = h*3+1; } for (;h>0;h=(h-1)/3){ for(int i=h;i<size;i++){ int temp = arr[i]; int j = i; while(j>h-1&&arr[jh]>temp){ arr[j]=arr[jh]; j-=h; } arr[j]=temp; } } } }