希尔排序，也称递减增量排序算法，是直接插入排序算法的一种高速而稳定的改进版本。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量=1(<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
1 package com.baozi.paixu; 2 3 import java.util.Arrays; 4 5 /** 6 * 希尔排序算法 7 * @author BaoZi 8 * @create 2019-05-15-17:41 9 */ 10 public class ShellSort { 11 public static void main(String[] args) { 12 int[] nums = new int[]{8, 3, 2, 1, 7, 4, 6, 5}; 13 System.out.println("........排序之前的数组........"); 14 System.out.println(Arrays.toString(nums)); 15 System.out.println("........排序之后的数组........"); 16 ShellSort.shellSort(nums); 17 System.out.println(Arrays.toString(nums)); 18 } 19 20 /** 21 * shellSort排序算法的实现 22 * 增量h=(h*3)+1; 这个增量公式是由Knuth给出的 23 * 24 * @param nums 25 */ 26 public static void shellSort(int[] nums) { 27 int len = nums.length; 28 //1、首先根据数组的长度确定增量的最大值 29 int h = 1; 30 //按h * 3 + 1得到增量序列的最大值 31 while (h <= len / 3) { 32 h = h * 3 + 1; 33 } 34 //进行增量查找和排序 35 while (h > 0) { 36 for (int i = h; i < len; i++) { 37 for (int k = i; k < len; k = k + h) { 38 //判断是否需要重新排序,如果小于k-h处的值，需要重新排序 39 if (nums[k] < nums[k - h]) { 40 int temp = nums[k]; 41 int j = k; 42 for (; j >= i && temp < nums[j - h]; j -= h) { 43 nums[j] = nums[j - h]; 44 } 45 nums[j] = temp; 46 } 47 } 48 } 49 h = (h - 1) / 3; 50 } 51 } 52 }
原文：https://www.cnblogs.com/BaoZiY/p/10931406.html