Java_经典算法之希尔排序

墨蓝 2023-07-04 12:38 10阅读 0赞

> 希尔排序是插入排序的一种更高效的改进版本，学习希尔排序请先去了解插入排序

### 一、希尔排序介绍 ###

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

1.  插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
2.  但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

**希尔排序的基本思想是：**

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

### 二、算法步骤（下面的箭头无实际意义，只是为了清楚区分谁和谁一个子序列） ###

假设我们要对int\[\] a = \{2 1 22 13 45 33 34 5 4\};这样一个数组进行排序

排序前需要将获取增量gap = 数组的长度 / 2（不一定非要除于2，只是一般都采用2，当然这个数字要小于数组的长度）。

那么我们要如何分子序列呢？这里gap = 4，从a\[0\]开始，a\[0\]会与a\[0+gap\],a\[0+2gap\](当然里面的下标要小于a数组的长度-1），

然后是a\[1\]与a\[1+gap\]一组.........直到a\[gap-1\]与a\[gap-1+gap\]分组完成,具体参考下图。

（其实我们也很容易发现，增量是多少，就有多少个子序列。）

![20200210224459830.png][]

这里分成了4个子序列（在图中同一序列的数字我已用相同的颜色表示出来了），然后将每个子序列通过插入排序排好，如下图：

![20200210225224305.png][]

所以第一轮排序后，

![20200210225356927.png][]

第二轮开始前，我们要对gap再次除以2，gap = 2,即分为两个子序列

![20200210225735440.png][]

如图所示，每个序列我已用相同颜色进行表示，我们再对每个子序列进行插入排序操作，

![20200210230555563.png][]

所以第二轮排序后，

![20200210230659804.png][]

第三轮开始前，我们要对gap再次除以2，gap = 1,即分为一个子序列

![20200210230935819.png][]

现在，只有一个子序列，我们对其进行一次插入排序就完成了

![20200210231201335.png][]

所以我们最终得到的数组就是1 ，2 ， 4，5，13，22，33，34，45

### 三、代码实现 ###

package com.rong.sort;
    
    import java.util.Arrays;
    
    public class ShellSort {
    
        public static int[] shellSort(int[] arr) {
            int[] sortArr = Arrays.copyOf(arr,arr.length);
            int gap = sortArr.length / 2;
           while (gap > 0) {
               for(int i = gap; i < sortArr.length ; i++) {
                   int temp = sortArr[i];
                   int j = i - gap;
                   while (j >= 0 && sortArr[j] > temp) {
                       sortArr[j+gap] = sortArr[j];
                       j-=gap;
                   }
                   sortArr[j+gap] = temp;
               }
               System.out.println();
               System.out.println("gap="+gap+"时");
               for (int val:sortArr){
                   System.out.print(val+"\t");
               }
               gap = gap / 2;
           }
            return sortArr;
        }
        public static void main(String[] args) {
            int[] sourceArr = {2,1,22,13,45,33,34,5,4};
            System.out.println("============排序前============");
            for(int val:sourceArr) {
                System.out.print(val+"\t");
            }
            System.out.println();
            System.out.println("============排序中============");
            int [] arr = shellSort(sourceArr);
            System.out.println();
            System.out.println("============排序后============");
            for(int val:arr){
                System.out.print(val+"\t");
            }
    
        }
    }

我们测试结果与上面进行比对，完全Ojbk

![20200210232056968.png][]

[20200210224459830.png]: https://img-blog.csdnimg.cn/20200210224459830.png
[20200210225224305.png]: https://img-blog.csdnimg.cn/20200210225224305.png
[20200210225356927.png]: https://img-blog.csdnimg.cn/20200210225356927.png
[20200210225735440.png]: https://img-blog.csdnimg.cn/20200210225735440.png
[20200210230555563.png]: https://img-blog.csdnimg.cn/20200210230555563.png
[20200210230659804.png]: https://img-blog.csdnimg.cn/20200210230659804.png
[20200210230935819.png]: https://img-blog.csdnimg.cn/20200210230935819.png
[20200210231201335.png]: https://img-blog.csdnimg.cn/20200210231201335.png
[20200210232056968.png]: https://img-blog.csdnimg.cn/20200210232056968.png