希尔排序是简单插入排序经过改进之后的一个更高效的版本，也叫缩小增量牌排序。插入排序存在一个问题：
sort时分步骤进行分析的方法 sort1是将sort进行抽象整合
package test1; import java.util.Arrays; import java.util.Random; /** * 希尔排序 */ public class ShellSort { public static void main(String[] args) { //int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; int arr[] = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i]= new Random().nextInt(80000); } long before = System.currentTimeMillis(); sort1(arr); long after = System.currentTimeMillis(); System.out.println((after-before) +"毫秒！"); } public static int[] sort(int[] arr) { int temp = 0; //1.第一轮，10/5 10个数分5组，每组两个，所以遍历5次 for (int i = 0; i < 5; i++) { //如果同组靠前的元素大于后面的，就交换位置 if (arr[i] > arr[i + 5]) { temp = arr[i]; arr[i] = arr[i + 5]; arr[i + 5] = temp; } } System.out.println(Arrays.toString(arr)); //排序结果：[3, 5, 1, 6, 0, 8, 9, 4, 7, 2] //2.第二轮，5/2 10个数分2组，遍历两次 for (int i = 0; i < 2; i++) { //每隔一个数就是一组,采用直接插入排序 for (int j = i + 2; j < arr.length; j += 2) { int num = arr[j]; int index = j - 2; while (index >= 0 && num < arr[index]) { arr[index+2] = arr[index]; arr[index] = num; index -= 2; } } } System.out.println(Arrays.toString(arr)); //排序结果：[0, 2, 1, 4, 3, 5, 7, 6, 9, 8] //3.第三轮，2/2=1 10个数分一组 for (int i = 0; i < 1; i++) { //从第二个数开始向后遍历 for (int j = i + 1; j < arr.length; j += 1) { //每次需要插入到有序列表的数字 int num = arr[j]; //每次需要插入的数字的前一个元素的下标，记录他是为了比较 int index = j - 1; //index=0时到达arr[0]，循环会使index==-1，出现下标越界，所以要进行判断index要大于=0 //用需要插入的元素与他的前一个元素进行比较，如果大，那么肯定比有序列表的所有数都大，所以直接排在后面 //如果小，则说明这个需要插入的元素在有序列表的某个位置，循环与有序列表的元素进行比较，找到自己的位置 while (index >= 0 && num < arr[index]) { //如果小，使待插入元素的位置后移 arr[index + 1] = arr[index]; //交换位置 arr[index] = num; //下标减一，继续向前查找 index -= 1; } } } //排序结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] System.out.println(Arrays.toString(arr)); return arr; } public static int[] sort1(int[] arr) { //把sort的三轮抽象在一起，gap代表组数 for (int gap = arr.length/2; gap>0 ; gap=gap/2) { for (int i = 0; i < gap; i++) { for (int j = i + gap; j <arr.length ; j+=gap) { int num = arr[j]; int index = j - gap; while (index >= 0 && num < arr[index]) { arr[index + gap] = arr[index]; arr[index] = num; index -= gap; } } } //System.out.println(Arrays.toString(arr)); } return arr; } }和以前一样用8万个随机数进行排序效率测试，结果如下： 简直快到飞起，冒泡要十几秒。。。希尔排序时间复杂度O(n^（1.3—2）)
