排序算法 —— 希尔排序（图文超详细）

分手后的思念是犯贱 2023-10-02 22:28 13阅读 0赞

#### 文章目录 ####

*  希尔排序（直接插入排序的优化）
 *   *  1.分组思想
     *  2.缩小增量的过程
     *  3.排序步骤
     *   *  3.1 排序五组数据的情况
         *  3.2 排序两组数据的情况
         *  3.3 排序一组数据的情况
     *  4.代码分析
     *   *  4.1 如何设置数据组数
         *  4.2 直接插入排序实现思路
     *  5. 整体代码实现

**排序算法：**

1、[直接插入排序][Link 1]

2、[选择排序][Link 2]

3、[堆排序][Link 3]

![38b26f44e9034d1ca94154edd9dac971.jpeg_pic_center][]

## 希尔排序（直接插入排序的优化） ##

希尔排序是将数据分组，将每一组进行插入排序。  
每一组排成有序后，最后整体就变有序了。  
  
![9aabbfa419ff40abbd7f301f0534ecd7.png_pic_center][]

### 1.分组思想 ###

![11a7d0a3ee6048c8b696fe4413de2531.png_pic_center][]  
上图中gap为5，说明要分成5组。  
这5组分别用了五种颜色的线条连接起来了。

> 第1组：9、4  
> 第2组：1、8  
> 第3组：2、6  
> 第4组：5、3  
> 第5组：7、5

为什么要采取上面的分组方法呢？换一种方法可以吗？  
例如：挨着的元素分为一组。  
![6ecd24cb77c7476d86d9e60bc6affab6.png_pic_center][]  
  
如果是上面的这种分组方式的话，排序之后会变成下面的情况。

![e106d7397071424f86281c60444779a0.png_pic_center][]  
  
如果是最开始的分组方法的话  
![9e25a9034aec423992d25768294f9f38.png_pic_center][]  
如果是按照最开始的分组思想分组的话，最后会排序成  
![807910326fce4ea6a2eabd6a85537962.png_pic_center][]  
可以发现左边都是叫小的数据，右边都是较大的数据。  
更方便把分成的每一个组进行插入排序。

### 2.缩小增量的过程 ###

前面gap为5的情况排序后会变成下面情况  
  
![7619ce632401402d9619d01a4bda9fb3.png_pic_center][]  
按照gap把数据分成了两组。  
  
当数据很大的时候，数据的间隔很大。  
小的数据会往前方，大的数据会往后放。

gap会逐渐缩小，间隔也会逐渐缩小。

整体的数据会更加趋于有序，这个时候使用直接插入排序效率会更高。

gap为2的时候会排序成下面情况  
![11575f22cca34c80b7883ccc9164c2fc.png_pic_center][]  
此时分为了1组，再排序一次后变成下面情况  
![ea4de8e8c2ad4616a5771547066277a9.png_pic_center][]  
此时的数据即为有序的。

### 3.排序步骤 ###

#### 3.1 排序五组数据的情况 ####

1.  gap为5，将数据分为5组，图中红色线画中的为第一组。定义一个 i 变量指向这一组的第二个数据，定义一个 j 变量指向 **i - gap** 的位置。![8d403486898846e4a94d7496df388805.png_pic_center][]
2.  将 i 下标的值放到定义的 tmp 中，然后与 j下标 的值比较。  
    若 j 下标的值较大，将 j 下标的值放到 **j + gap** 的位置。  
    ![037c0d632d7448a989c4e53e896791c7.png_pic_center][]  
    执行后：  
    ![20819167f88641279c384200232dc1dc.png_pic_center][]
3.  j 变量向 **j - gap** 位置走，若这个位置的下标为负数。  
    则要将 tmp 的值放到 **j + gap**的位置。  
    ![dc0defaef654488888af48c1e6596a2d.png_pic_center][]  
    j 变量此时在-5下标处，要将 tmp 的值放到 **j + 5**的位置。  
    ![9513a7c4442b467a9f7a1b283515e246.png_pic_center][]  
    这一组数据此时为有序了。  
    排序下一组数据，\*\*i++\*\*即可，j 变量依然是在 **i - gap** 的位置。  
    后面4组数据类似，不在演示。  
    最终排序结果是：  
    ![c09b03bdd6b94837b4fee65df6948aee.png_pic_center][]

#### 3.2 排序两组数据的情况 ####

1.  此时 gap 为2，数据此时分为了两组。第一组由红色线画出（4、2、5、8、5），第二组由蓝色线画出（1、3、9、6、7）。  
    i 变量指向这一组的第二个数据， j 变量指向 **i - gap** 的位置。  
    ![3ea66600770147378983ab034d12c5f6.png_pic_center][]
2.  将 i 下标的值放到定义的 tmp 中，然后与 j下标 的值比较。  
    若 j 下标的值较大，将 j 下标的值放到 **j + gap** 的位置。  
    ![efcf7aa3fa094d13a3376803df16a31d.png_pic_center][]  
    执行后：  
    ![cfb1406edc4945c3a237c4102f315f37.png_pic_center][]
3.  j 变量向 **j - gap** 位置走，若这个位置的下标为负数。  
    则要将 tmp 的值放到 **j + gap**的位置。  
    ![56b214f25a8b4cd9b433ab5d887c6061.png_pic_center][]  
    j 变量此时在-2下标处，要将 tmp 的值放到 **j + 2**的位置。  
    ![78761bc9be7a49b0b766e82d42d7fc61.png_pic_center][]  
    这一组数据中的 2 和 4 此时为有序了。  
    排序下一组数据，**i++** 即可，j 变量依然是在 **i - gap** 的位置。  
    后面剩下的数据类似，不在演示。  
    最终排序结果是：  
    ![852974ee3dd94210a94d3d16afbb1592.png_pic_center][]

#### 3.3 排序一组数据的情况 ####

1.  i 变量指向第二个数据， j 变量指向 **i - gap** 的位置。  
    ![80cbbc8439854bb5886e2cbd175390fe.png_pic_center][]
2.  将 i 下标的值放到定义的 tmp 中，然后与 j下标 的值比较。  
    若 j 下标的值较大，将 j 下标的值放到 **j + gap** 的位置。  
    ![e0f5bee0fc5b491c8d9daa4c72bb5079.png_pic_center][]  
    执行后：  
    ![d419ecda04294686a1c2a280e707d807.png_pic_center][]
3.  j 变量向 **j - gap** 位置走，若这个位置的下标为负数。  
    则要将 tmp 的值放到 **j + gap**的位置。  
    ![62529b52f58245a4b70ce6ff3737ebbf.png_pic_center][]  
    j 变量此时在-1下标处，要将 tmp 的值放到 **j + 1**的位置。  
    ![45c515d245614a62ad3795ab61b941c7.png_pic_center][]  
    此时 前两个数据有序了，后面的数据排序过程类似。  
    排序下一组数据，**i++** 即可，j 变量依然是在 **i - gap** 的位置。  
    最终结果是：  
    ![73f3c11fc10d41578c86a2b27e7ad4fd.png_pic_center][]

### 4.代码分析 ###

#### 4.1 如何设置数据组数 ####

1.  定义 gap 将数组的长度赋值给这个变量。

int gap = array2.length;//为数组的长度 - 为10

1.  设置循环，每次使 gap 除以2来得到5、2、1三个组。
2.  在循环内部调用直接插入排序方法。

while (gap > 1) {
        
         gap /= 2;//先是分成了5组，然后是2组，再是1组
         shell(array2, gap);//调用直接插入排序方法
     }

#### 4.2 直接插入排序实现思路 ####

1.  遍历数组，i 变量从 gap 下标位置开始

for (int i = gap; i < array2.length ; i++){
        
    }

1.  j 变量从 **i- gap** 位置开始

int j = i - gap;

1.  j 变量要每次减去 gap 个位置，j 此时的位置要是负数就比较 j 和 tmp 的值。

for (; j >= 0; j-=gap){
        
    }

1.  j 和 tmp 如何比较

if (array2[j] > tmp) {
        
         //j下标的值大，将j下标的值放到j变量加上一个gap的位置上
         array2[j + gap] = array2[j];
     }else {
        
         //j下标的值较小，j下标的值要直接放到j变量加上一个gap的位置上
         break;
     }

1.  j 下标为负数的情况

//此时j下标的值是负数了，将tmp的值放到j变量加上一个gap的位置上
     array2[j + gap] = tmp;

更加详细的直接插入排序讲解请参考我的另一篇文章。

![f3998f481edf45f482e88650ad3af94c.gif_pic_center][]  
文章链接：http://t.csdn.cn/rBDzh

### 5. 整体代码实现 ###

public static void shellSort(int[] array2) {
        
         int gap = array2.length;//为数组的长度 - 为10
         while (gap > 1) {
        
             gap /= 2;//先是分成了5组，然后是2组，再是1组
             shell(array2, gap);//调用直接插入排序方法
         }
     }
    
     //实现直接插入排序方法
     public static void shell(int[] array2, int gap) {
        
         //i下标从第一组的第二个数据开始
         for (int i = gap; i < array2.length ; i++) {
        
             int tmp = array2[i];//tmp存放i下标的值
             int j = i - gap;//j下标为i-gap个位置
             //j每次-gap个位置
             for (; j >= 0; j-=gap) {
        
                  if (array2[j] > tmp) {
        
                    //j下标的值大，将j下标的值放到j变量加上一个gap的位置上
                    array2[j + gap] = array2[j];
                  }else {
        
                     //j下标的值较小，j下标的值要直接放到j变量加上一个gap的位置上
                     break;
                  }
              }
              //此时j下标的值是负数了，将tmp的值放到j变量加上一个gap的位置上
              array2[j + gap] = tmp;
          }
     }

![5017eb9349da486196f77b95fb710c91.gif_pic_center][]

[Link 1]: https://blog.csdn.net/m0_63033419/article/details/127456106
[Link 2]: https://blog.csdn.net/m0_63033419/article/details/127607798
[Link 3]: https://blog.csdn.net/m0_63033419/article/details/127644252
[38b26f44e9034d1ca94154edd9dac971.jpeg_pic_center]: https://img-blog.csdnimg.cn/38b26f44e9034d1ca94154edd9dac971.jpeg#pic_center
[9aabbfa419ff40abbd7f301f0534ecd7.png_pic_center]: https://img-blog.csdnimg.cn/9aabbfa419ff40abbd7f301f0534ecd7.png#pic_center
[11a7d0a3ee6048c8b696fe4413de2531.png_pic_center]: https://img-blog.csdnimg.cn/11a7d0a3ee6048c8b696fe4413de2531.png#pic_center
[6ecd24cb77c7476d86d9e60bc6affab6.png_pic_center]: https://img-blog.csdnimg.cn/6ecd24cb77c7476d86d9e60bc6affab6.png#pic_center
[e106d7397071424f86281c60444779a0.png_pic_center]: https://img-blog.csdnimg.cn/e106d7397071424f86281c60444779a0.png#pic_center
[9e25a9034aec423992d25768294f9f38.png_pic_center]: https://img-blog.csdnimg.cn/9e25a9034aec423992d25768294f9f38.png#pic_center
[807910326fce4ea6a2eabd6a85537962.png_pic_center]: https://img-blog.csdnimg.cn/807910326fce4ea6a2eabd6a85537962.png#pic_center
[7619ce632401402d9619d01a4bda9fb3.png_pic_center]: https://img-blog.csdnimg.cn/7619ce632401402d9619d01a4bda9fb3.png#pic_center
[11575f22cca34c80b7883ccc9164c2fc.png_pic_center]: https://img-blog.csdnimg.cn/11575f22cca34c80b7883ccc9164c2fc.png#pic_center
[ea4de8e8c2ad4616a5771547066277a9.png_pic_center]: https://img-blog.csdnimg.cn/ea4de8e8c2ad4616a5771547066277a9.png#pic_center
[8d403486898846e4a94d7496df388805.png_pic_center]: https://img-blog.csdnimg.cn/8d403486898846e4a94d7496df388805.png#pic_center
[037c0d632d7448a989c4e53e896791c7.png_pic_center]: https://img-blog.csdnimg.cn/037c0d632d7448a989c4e53e896791c7.png#pic_center
[20819167f88641279c384200232dc1dc.png_pic_center]: https://img-blog.csdnimg.cn/20819167f88641279c384200232dc1dc.png#pic_center
[dc0defaef654488888af48c1e6596a2d.png_pic_center]: https://img-blog.csdnimg.cn/dc0defaef654488888af48c1e6596a2d.png#pic_center
[9513a7c4442b467a9f7a1b283515e246.png_pic_center]: https://img-blog.csdnimg.cn/9513a7c4442b467a9f7a1b283515e246.png#pic_center
[c09b03bdd6b94837b4fee65df6948aee.png_pic_center]: https://img-blog.csdnimg.cn/c09b03bdd6b94837b4fee65df6948aee.png#pic_center
[3ea66600770147378983ab034d12c5f6.png_pic_center]: https://img-blog.csdnimg.cn/3ea66600770147378983ab034d12c5f6.png#pic_center
[efcf7aa3fa094d13a3376803df16a31d.png_pic_center]: https://img-blog.csdnimg.cn/efcf7aa3fa094d13a3376803df16a31d.png#pic_center
[cfb1406edc4945c3a237c4102f315f37.png_pic_center]: https://img-blog.csdnimg.cn/cfb1406edc4945c3a237c4102f315f37.png#pic_center
[56b214f25a8b4cd9b433ab5d887c6061.png_pic_center]: https://img-blog.csdnimg.cn/56b214f25a8b4cd9b433ab5d887c6061.png#pic_center
[78761bc9be7a49b0b766e82d42d7fc61.png_pic_center]: https://img-blog.csdnimg.cn/78761bc9be7a49b0b766e82d42d7fc61.png#pic_center
[852974ee3dd94210a94d3d16afbb1592.png_pic_center]: https://img-blog.csdnimg.cn/852974ee3dd94210a94d3d16afbb1592.png#pic_center
[80cbbc8439854bb5886e2cbd175390fe.png_pic_center]: https://img-blog.csdnimg.cn/80cbbc8439854bb5886e2cbd175390fe.png#pic_center
[e0f5bee0fc5b491c8d9daa4c72bb5079.png_pic_center]: https://img-blog.csdnimg.cn/e0f5bee0fc5b491c8d9daa4c72bb5079.png#pic_center
[d419ecda04294686a1c2a280e707d807.png_pic_center]: https://img-blog.csdnimg.cn/d419ecda04294686a1c2a280e707d807.png#pic_center
[62529b52f58245a4b70ce6ff3737ebbf.png_pic_center]: https://img-blog.csdnimg.cn/62529b52f58245a4b70ce6ff3737ebbf.png#pic_center
[45c515d245614a62ad3795ab61b941c7.png_pic_center]: https://img-blog.csdnimg.cn/45c515d245614a62ad3795ab61b941c7.png#pic_center
[73f3c11fc10d41578c86a2b27e7ad4fd.png_pic_center]: https://img-blog.csdnimg.cn/73f3c11fc10d41578c86a2b27e7ad4fd.png#pic_center
[f3998f481edf45f482e88650ad3af94c.gif_pic_center]: https://img-blog.csdnimg.cn/f3998f481edf45f482e88650ad3af94c.gif#pic_center
[5017eb9349da486196f77b95fb710c91.gif_pic_center]: https://img-blog.csdnimg.cn/5017eb9349da486196f77b95fb710c91.gif#pic_center