希尔排序

希尔排序是插入排序的更高效改进版本，又称“缩小增量排序”。

先回顾一下插入排序

将数组看成两部分，有序序列和无序序列 初始时，第一个数已有序，从第二个数开始，用一个变量保存该数，在有序序列中找到该数正确的位置插入。第一趟插入：num = a[1]，从该数的前一个数开始依次比较直到第一个数，如果逆序，就将数往后移。 /** * @author ：Mrs.You * @date ：2020/10/19 11:30 * @description：插入排序 */ public class InsertSort { public static void main(String[] args) { int[] a = {324,543,32,56,259,9}; insertSort(a); } public static void insertSort(int[] a){ int num; //待插入数 int index; //应该插入位置的下标 for (int i = 1; i < a.length; i++){ num = a[i]; System.out.println("第"+i+"趟开始："+Arrays.toString(a)); for (index = i-1; index >=0;){ if (a[index] > num){ //如果逆序，数往后移，继续向前比较 a[index+1] = a[index]; index--; System.out.println(Arrays.toString(a)); }else{ //如果待排序数num大于a[index],就跳出循环，不需要再往前比较，因为前面的数都是有序的。 break; } } //循环结束后此时index的位置是待插入位置的前一个位置 if (index != i - 1){ //如果index没有变化说明num的位置不用变 a[index + 1] = num; } System.out.println("第"+i+"趟结束："+Arrays.toString(a)); } } }

希尔排序——交换法原理

对待排序数组进行分组，一般以1/2数组长度为划分依据；第一次将数据元素分为gap = a.length/2组，以a.length/2为步长划分数据元素分组；第二次将数据元素分为gap = a.length/2/2组，以a.length/2/2为步长划分数据元素分组；以此类推，直到gap<1。我们将数据分组后，就是将同一组的数据看成一个序列，在这个序列内进行排序。

文字的说明过于抽象，还是直接上代码来看看

public class ShellSort { public static void main(String[] args) { int[] a = {8, 9, 1, 7, 2, 5, 4, 6, 0}; System.out.println("初始：" + Arrays.toString(a)); shellSort(a); } public static void shellSort(int[] a) { int temp; for (int gap = a.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < a.length; i++) { for (int j = i - gap; j >= 0; j -= gap) { System.out.println("a[" + (j + gap) + "]=" + a[j + gap] + " < a[" + j + "]=" + a[j] + "? " + (a[j] > a[j + gap])); if (a[j+gap] < a[j]) { temp = a[j]; a[j] = a[j + gap]; a[j + gap] = temp; } } } System.out.println("gap=" + gap + " 排序后：" + Arrays.toString(a)); } } } 外层循环显然是用于控制步长；中间循环因为前面例子说了下标从0到gap-1的数正好是每组分组的第1个数据，默认在组内是有序的，所以从下标gap开始，直到数组末尾；内层循环是为当前的这个数据元素找到它在组内的正确位置。

用一个例子来理解一下上段代码：

对 {8, 9, 1, 7, 2, 5, 4, 6, 0}进行希尔排序 步长gap=9/2=4组，第1组：{8, 2, 0} 第2组：{9, 5} 第3组：{1, 4} 第4组：{7, 6}可以发现下标从0到gap-1的数正好是每组分组的第1个数据，因此从下标为gap的数开始与其组内前面的数进行比较，交换。第一次： 以第1组为例 当下标i为4时，就将a[4]（2）和a[0]（8）进行比较并交换，此时组内是{2, 8, 0}，组内前面没有数据了；当下标到8时，就将a[8]（0）和a[4]（8）进行比较并交换，此时组内是{2, 0, 8}，组内前面还有数据，还要再进行比较，将a[4]（0）和a[0]（2）进行比较并交换;此时组内有序{0, 2, 8} 这里很重要的一点就是，当第一次进行比较完之后，还要再看看组内前面还有没有数据需要进行比较，要寻找到那个数在组内的正确位置。注意：这里是每次比较发现逆序之后就直接交换位置。 第一次排序后：{0, 5, 1, 6, 2, 9, 4, 7, 8} 第二次： 步长gap=9/2/2=2组，第1组：{0, 1, 2, 4, 8} 第2组：{5, 6, 9, 7}第二次排序后：{0, 5, 1, 6, 2, 7, 4, 9, 8} 第三次： 步长gap=9/2/2/2=1组，第1组：{0, 5, 1, 6, 2, 7, 4, 9, 8}第三次排序后：{0, 1, 2, 4, 5, 6, 7, 8, 9}

为了可以看得更明白，我把比较的那句打印出来，用以上的例子执行代码

可以看到，第一次分组排序和上面分析的一样，下标为8时，第一次比较交换后，因为组内前面还有数据，又进行了一次比较并交换。

优化

看到第三次分组后的结果：

可以看到，当i=8时，要将a[8]插入到前面这个已经有序的数组中，而第一次比较交换8和9后，整个数组就有序了，因此可以优化一下，当出现一次待插入数和被比较数不满足逆序后就跳出循环。

改进后：

public static void shellSort(int[] a) { int temp; for (int gap = a.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < a.length; i++) { for (int j = i - gap; j >= 0; j -= gap) { if (a[j + gap] < a[j]) { temp = a[j]; a[j] = a[j + gap]; a[j + gap] = temp; }else { break; } } } System.out.println("gap=" + gap + " 排序后：" + Arrays.toString(a)); } }

不要小看那个break，用下面这段代码测试一下加了break和没加break排序10万个数据和100万个数据的速度差异

public static void main(String[] args) { /* int[] a = {8, 9, 1, 7, 2, 5, 4, 6, 0}; System.out.println("初始：" + Arrays.toString(a)); shellSort2(a); System.out.println(Arrays.toString(a));*/ int[] a = new int[1000000]; for (int i = 0; i < a.length; i++) { a[i] = (int)(Math.random()*1000000); } long start = System.currentTimeMillis(); shellSort(a); long end = System.currentTimeMillis(); System.out.println("希尔排序加了break排序10万个数共花费：" + (end - start) / 1000.000 + "秒");

把else { break; }注释掉再跑一遍：

最后这个结果在我的机器上跑了两次都是696秒，等了好久…可见这个break有多重要~~

希尔排序——移位法

交换法是每发现一次逆序就交换两个元素。而移位法是将分组后的元素在其组内进行插入排序，将待插入的数据存放起来，向前比较，如果逆序就将前面的数往后移，再往前比较，直到找到正确的位置后存放起来的数据放到该位置上。

public static void shellSort2(int[] a){ int num; int j; for (int gap = a.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < a.length; i++){ //保存待插入数 num = a[i]; //待插入数num和其前面的数进行比较，因前面的数已有序，故如果比较到一次num < a[j] == flase就退出 for (j = i-gap;j >=0; j-=gap){ if (num < a[j]){ //后移 a[j+gap] = a[j]; }else { break; } } //循环结束后num正确的位置应该是j+gap，因为在j不满足的时候才会退出，说明a[j]是比num小的数。 if (j+gap != i){ a[j+gap] = num; } } } }

时间复杂度测试

前面说了希尔排序是插入排序的高效改进版本，那么这个三个循环嵌套的代码真的能高效吗？

让我们来分别对插入排序、希尔排序交换法和希尔排序移位法进行一个排序10万个数据、100万个数据的时间测试。

public static void main(String[] args) { int[] a = new int[100000]; for (int i = 0; i < a.length; i++) { a[i] = (int) (Math.random() * 10000000); } long start = System.currentTimeMillis(); insertSort(a); long end = System.currentTimeMillis(); System.out.println("插入排序10万个数共花费：" + (end - start) / 1000.000 + "秒"); for (int i = 0; i < a.length; i++) { a[i] = (int) (Math.random() * 10000000); } start = System.currentTimeMillis(); ShellSort.shellSort(a); end = System.currentTimeMillis(); System.out.println("希尔排序交换法10万个数共花费：" + (end - start) / 1000.000 + "秒"); for (int i = 0; i < a.length; i++) { a[i] = (int) (Math.random() * 10000000); } start = System.currentTimeMillis(); ShellSort.shellSort2(a); end = System.currentTimeMillis(); System.out.println("希尔排序移位法10万个数共花费：" + (end - start) / 1000.000 + "秒"); }

可见希尔排序要远远快过插入排序，移位法和交换法相差不大。