希尔排序实际上也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
希尔排序是把一组数据按下表的一定增量分组，对每组使用直接插入排序算法进行排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便种植
有一组数据{8，9，1，7，2，3，5，4，6，0}，从小到大进行排序
代码实现
public class ShellSort { public static void main(String[] args) { // int[] arr = {3, 5, 1, 6, 0, 8, 9, 4, 7, 2}; int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; sort2(arr); // int[] arr = new int[8000000]; // for (int i = 0; i < 8000000; i++) { // arr[i] = (int) (Math.random() * 100000); // } // // long start = System.currentTimeMillis(); // sort(arr); // long end = System.currentTimeMillis(); // System.out.println(end - start); System.out.println(Arrays.toString(arr)); } private static void sort2(int[] arr){ int step = arr.length; while ((step /= 2) >= 1){ //该循环控制共分了多少组 for (int i = 0; i < step ; i++){ //该循环控制每组有多少个数需要比较 //arr.length / step 为每组的元素个数 -1后则为需要参与比较的数 for (int j = 0; j < (arr.length / step) -1; j++) { int insertValue = arr[i+step*(j+1)]; int tempIndex = i+step*(j+1); while (tempIndex > i && insertValue < arr[tempIndex -step]){ arr[tempIndex] = arr[tempIndex -step]; tempIndex -= step; } arr[tempIndex] = insertValue; } } } } }