Java排序算法之希尔排序

矫情吗；* 2022-04-12 11:40 158阅读 0赞

这几天看了一点希尔排序，据说它是插入排序的优化，但是我愣是没看出来到底优化在什么地方，从原理上分析，希尔排序也就是将一组数按照一定的方式切分成不同的组，然后各个组进行插入排序，说到底，底层还是插入排序。

我们先看看它的原理：将一组含n个元素的数，不停的除以2取“间隔数”，然后隔着间隔数取数成组，在对这个组进行插入排序，直到这个间隔数为1为止，也就是对整体数组进行插入排序，据说可以减少插入排序的次数。下面画图演示：

假如有一组数:【**26, 53, 67, 48, 57, 13, 48, 32, 60, 50**】，共10个元素，对其进行希尔排序；

先取第一个间隔数：10/2=5，从首元素开始，每隔5个元素取一个，组成组：

![20181203113103239.png][]

组成【26,13】，【53,48】，【67,32】，【48,60】，【57,50】；对这5个组分别进行插入排序：

为【13,26】，【48,53】，【32,67】，【48，60】，【50,57】；然后将它们放回到原来的位置，为：

【13, 48, 32, 48, 50, 26, 53, 67, 60, 57】；

然后取第二组间隔数：10/4=2，从首元素开始，每隔2个元素取一个，组成组：

![20181203142137354.png][]

组成【13,32,50,53,60】和【48,48,26,67,57】，然后对这两组数进行插入排序，为：

【13,32,50,53,60】和【26,48,48,57,67】；然后将它们放回到原来的位置，为：

【13,26,32,48,50,48,53,57,60,67】

然后取第三组间隔数：10/8=1，从首元素开始，每隔1个元素取一个，组成组，也就是典型的插入排序了，这里不画图演示了，排序结果为：【13 ，26， 32， 48， 48 ，50， 53， 57， 60， 67】

一下用代码演示：

/**
         * 希尔排序
         */
        @Test
        public void test4(){
            int[] data = new int[] {26, 53, 67, 48, 57, 13, 48, 32, 60, 50};
            int j = 0;
            int temp = 0;
            for (int increment = data.length / 2; increment > 0; increment /= 2) {
                System.out.println("increment:" + increment);
                for (int i = increment; i < data.length; i++){
                    temp = data[i];
                    for (j = i - increment; j >= 0; j -= increment){
                        if (temp < data[j]){
                            data[j + increment] = data[j];
                        } else {
                            break;
                        }
                    }
                    data[j + increment] = temp;
                }
                for (int i = 0; i < data.length; i++){
                    System.out.print(data[i] + " ");
                }
                System.out.println();
            }
        }

运行代码是：

![20181203143328379.png][]

[20181203113103239.png]: /images/20220412/bdf3eebf55ad4b97907c1299e90bd476.png
[20181203142137354.png]: /images/20220412/d2ea45d810e9411ea259b2d4cc62d95e.png
[20181203143328379.png]: /images/20220412/9d9b4661539f4515851bb8d99e9e62c3.png