带你彻底搞定希尔排序是个什么情况

客官°小女子只卖身不卖艺 2022-06-04 23:55 94阅读 0赞

首先希尔排序是怎么来的，为什么叫希尔排序。

这个算法其实是一个叫什么shell发明的。我们中文翻译过来的。所以名称由来搞定了吧。

那么希尔排序有个希尔增量序列，这个是什么意思，比如我们有个数组

![这里写图片描述][SouthEast]

这个增量就是数组索引间隔比如我的希尔增量是5，那么我们在排序的时候就是比如81这个数就作为手里拿的第一张牌，先不动，然后我们在这个牌的基础上+5，就找到了35这个牌，进行比较35小，就把35放到81这个位置，而我们开始还是先要保存这个临时数据81，在拿81和41比较还是41小，就把41放在35那个索引位置也就是索引为5的位置。然后没有可比较的元素了，我们就把那个临时值81放在索引值为10的地方。  
就完成了第一次5间隔或者叫5增量的排序，为什么叫增量序列呢，因为我们进行了5增加排序后还是3增量排序，还有1增量排序 是一个系列。当增量为1的时候，我们是两两比较会最终有序。

现在问题的主题来了，我们讨论希尔排序之前我希望你已经熟悉了直接插入排序的，因为我们的希尔排序其实就是在插入排序的基础上进行的。什么呢，就是说没有增量的这个过程，还是可以有序，只是这样的话可能性能没有那么高，因为希尔排序会对序列进行大体的有序，这样真正在直接插入排序的时候就会少了很多循环代码。具体减少分析，比如我们的数组如果差不多有序，我们在排序的时候其实我们比较次数不会减少，但是我们的移动数据次数会大大减少的。

下面上实现的伪代码：主要学习思想，我们用很多文字描述每段代码的作用

//希尔排序算法  待排序数组array 数组元素n
    void Shell_Sort(int array[], int n)
    {
         //得到希尔排序增量值d
         //补充下小知识点我们是根据增量值d = n/2开始进行直接插入排序假如我们设n = 10 那么d = 5
         //第二次d = 5/2 = 2  第三趟排序 d = 1 其实这个时候增量为1的时候进行的插入排序是彻底的
         //那么肯定会有序，因此我们需要跑的次数就很清楚
         int d = n/2;
    
         //增量为1以上我们就一直循环进行直接插入排序
         while(d >= 1)
         {        
              //开始直接插入排序算法
              //我们还是假定第一个有序，因此我们开始拿到第二个元素和前面的元素一一比较
              for(int i = d; i < n; i++)
              {
                     //定义临时内存保存当前被排序的元素
                     int temp = array[i];
                     //开始得到当前元素的前面的元素索引j方便后续比较啊
                     int j = i - d;
    
                     //正式通过循环进入比较的过程大战
                     while(j >= 0) //我们的索引必须是大于==0的，否则就退出咯
                     {
                           //前面的元素大于当前的
                          if(temp < array[j])
                          {
                               //开始元素移动到后面
                               array[j + d] = array[j];
    
                               //并且将索引按照增量值减少一格
                               j = j -d;
                          }else  // 前面的元素大于当前的元素
                          {
                                //开始将临时数据写入空出来的位置
                                array[j + d] = temp;
                                break;
                          }
                     }
                     //第一趟增量比较完毕，开始设置第二趟 减少增量
                     d = d/2;
              }
         }
    }

[SouthEast]: /images/20220605/4293d60a1a6d4247ad0d00864df2be77.png