排序算法（四）希尔排序

排序算法（四）希尔排序

之前说的是插入排序，虽然插入排序的效率嘛已经说是可以的了，但是插入排序有一个明显的漏动。比如说给定的数组如果是 1 2 3 4 5 6 7 8 9 0使用插入排序要将这个0移动到数组的最前面还是非常费力的。也就说是如果有很多小数据位于数组的末端，插入排序的效率就会极大的降低。而这次要说的希尔排序就是插入排序的一种，也就死来解决这个问题的。

希尔排序的基本介绍

希尔排序虽然是插入排序的一种优化，但是希尔排序是不稳定的，插入排序是稳定的。于此类似的是快速排序是冒泡排序的优化，但是快速排序不稳定，冒泡排序稳定。不过。。稳定性这个玩意我到现在还没有用到过。

希尔排序的基本思路

希尔排序的基本思路就是分组进行插入排序。就还比如说上面的那个数组 1 2 3 4 5 6 7 8 9 0，我们将其分为五组，1 6 ，2 7.3 8.4 9.5 0。对这五组数据进行插入排序，那么清晰的可以看见0到前面却。然后将数据分为两组，继续插入排序。再将数据分为一组(此时就是插入排序了)进行排序就完事了。既然希尔排序中包含这插入排序那为啥希尔排序的速度还比插入排序快啊，希尔排序的前面的几次分组将小的数据往前面进行了移动，最后的那次插入排序移动的次数是很少的。所以说希尔排序是一种较为高效的算法。

下面的图片基本上就讲的比较清楚了。

再来一个图片演示一下

希尔排序和插入排序一样，都有交换法和移动法的实现，我们就分别都用代码演示一下。

希尔排序——交换法代码实现

//这也是插入排序的一种 ,因为插入排序是 ,如果小的数在后面的话 插入排序的效率特别的低,所以出现了希尔排序，是插入排序的一种改进
    public static void shellSort(int[] arr) {
        int temp = 0;
//        System.out.println("原来的数组："+Arrays.toString(arr));
        // 这里的gap指的是不同的组数据之间的距离。
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i; j >= gap; j -= gap) {
                    // 交换的次数太多了 太浪费时间
                    if (arr[j] < arr[j - gap]) {
                        temp = arr[j];
                        arr[j] = arr[j - gap];
                        arr[j - gap] = temp;
                    }else break; // 分组进行插入排序，如果上面的条件不成立就说明已经插入到了指定的位置。
                }
            }
//            System.out.println("第x次排序：" + Arrays.toString(arr));
        }
    }

代码说明：

1. gap是什么？

   gap指的是同一组当中相邻的元素之前的距离。初始值是arr.length/2，以后每次都除以2，这就是为什么我在一开始的那个数组中先分为五组再分为两组最后再分为一组。等到gap等于1也排序完成了之后，gap/2变成了0，此时排序完成，就可以退出循环了。

2. i和j代表着什么含义？

   • i从gap开始是为什么？ i代表的是每组元素的后面无序元素，从每组第二个元素开始。这就好比插入排序，每一组的第一个元素是有序的，而后面的元素是无序的，我们要将后面的无序的数据插入到前面的有序的数据中。其实我们完全可以写了个函数insertSort(int arr[], int gap)。gap等于1的时候就是上面篇博客当中的插入排序的算法。
   • j就是要插入的元素所在的位置，只不过这一次他前面的那个元素不再是j-1，而是j-gap，
   • 如果理解了上篇博客的插入排序的思路的话，这个希尔排序也是非常容易理解的。

3. 有三层for循环，效率为什么高？

   有三层for循环并不代表这时间复杂度就是O(n^3^)，第一层for循环每次都除以2，时间复杂度是O(log2n)。第二层的for循环每次都加1，时间复杂度是O(n)，第三层for循环的每次都减去gap，复杂度也在O(logn)左右。所以这个算法的时间复杂度是O(nlog^2^n)。数据量越大，越是比O(n^2^)的排序算法来的优越。

希尔排序——移位法代码实现

    // 和插入排序法相似，希尔排序也有两种实现的方式，一个是上面的那个交换法，另一个就是下面的移动法。
    // 采用移动法 对交换式的希尔排序进行改进 思路与之前的插入排序是相似的
    public static void shellSortPlus(int[] arr) {
        for (int gap = arr.length/2; gap > 0; gap/=2) {
            for (int i = gap; i < arr.length; i++) {
                int insertIndex = i;
                int insertVal = arr[i];
                    while (insertIndex-gap >=0 && insertVal < arr[insertIndex-gap]) {
                        arr[insertIndex] = arr[insertIndex-gap];
                        insertIndex -= gap;
                    }
                    arr[insertIndex] = insertVal;
            }
        }
    }

代码说明：

其实这个代码也没有什么要说明的，这就是插入排序的套了个gap嘛。不懂的可以去看看插入排序的那个算法去。嘤嘤嘤~

希尔排序的测试

测试环境及工具：我的电脑 Huawei MateBook 13+JDK1.8+Eclipse

测试手段：随机生成80,000个和8,000,000个[0, 800000）的整数的数组进行排序，观察所花费的时间

测试代码：

public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random() * 800000);
            arr[i] = new Random().nextInt(800000);
        }
//        System.out.println(Arrays.toString(arr));
        long start_time = System.currentTimeMillis();
        shellSort(arr);
//        shellSortPlus(arr);
        long end_time = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("Time :" + (end_time - start_time) + "ms");
    }

交换法

80,000数据时：

• Time : 14ms

• Time : 16ms

• Time : 17ms

8,000,000数据时：

• Time : 2008ms

• Time : 2018ms

• Time : 1973ms

移位法

80,000数据时：

• Time : 17ms

• Time : 17ms

• Time : 15ms

8000000数据时：

• Time : 1868ms

• Time : 1824ms

• Time : 1873ms

总结

希尔排序虽然只是对冒泡排序的一个小小的改进，但是看到了这个希尔排序的速度后，这肯定是要惊呆了！！什么！！！排序八百万个数据也就和插入排序法排序八万个差不多！什么！！冒泡排序法，，它。。要寻短见？ 这不能喽，程序员需要冒泡排序法！你排七八个数据难道还要写归并排序，堆排序嘛，还不是一个冒泡排序写的舒服~~