Data Structures and Algorithms — Hill Sort (Java implementation)

Hill sort is a variant of insertion sort algorithm, proposed by D.L.Shell in 1959, so named Hill sort.

Insert sort is an unstable sorting algorithm with O(n^2) time complexity. It is unstable because the sorting efficiency of insert sort is very fast when it deals with nearly ordered arrays, while the sorting efficiency is n square when it deals with completely unordered arrays. Hill sort is an excellent algorithm to solve the problem that insertion sort is too slow in dealing with completely unordered arrays.

The idea of Hill sort is that, on the basis of insert sort, the index interval of insert array is enlarged, and the interval size is H. The minimum value of h is 1, and the maximum value is h*3+1 is less than the array length.

• Hill sort (Java implementation)

private static void shellsort(int[] arr) {
	int h = 1;
	while((h*3+1) < arr.length) {
		h = h*3+1;
	}
	while(h > 0) {
		for(int i = h; i < arr.length; i++) {
			int insertValue = arr[i];
			int j = i;
			for(j = i; j > h-1 && arr[j-h] > insertValue; j = j-h ) {
				arr[j] = arr[j-h];
			}
			arr[j] = insertValue;
		}
		h = (h-1) /3; }}Copy the code