JS实现希尔排序（代码+讲解）

这一篇我们说一下希尔排序，当然了如果学习希尔排序 那么就要知道插入排序的原理，因为希尔排序算的上是插入排序的进化版 如果没有学习过插入排序 那么就给一个传送门！

https://blog..net/weixin_46726346/article/details/112912649?spm=1001.2014.3001.5501

学习了插入排序我们就可以对希尔排序进行讲解原理并实现了。 我们假设一下我们有这样一个数组 首先我们要确定一个增量，这里面我们一般用数组长度的一半为初始值。 那这里我们的增量初始值应该为3

现在我们用这个3来把这个数组分为3对 然后对每一对进行插入排序，得到一个半排序的数组 然后增量为刚才增量的一半（为向下取整）

此时增量为1，就是直接插入排序就可。 所以这就是希尔排序的全部过程

现在我们用代码来实现一下

function sort(arr){
          
   
            //第一趟循环，确定增量
            for(let gap = parseInt(arr.length/2);gap>0;gap = parseInt(gap/2)){
          
   
                //第二层循环，找到每个块对应的序列
                for(let i=gap;i<arr.length;i++){
          
   
                    let j=i;
                    let empty = arr[j]
                    //使用插入排序对对应的序列进行排序
                    while(j - gap>=0 &&empty <arr[j - gap]){
          
   
                        arr[j] =arr[j-gap];
                        j -= gap;
                    }
                    arr[j] = empty;

                }
            }
        }

第一趟循环确定好增量，并且分好组 第二层循环和第三层循环进行插入排序。

OK，这样对于JS的希尔排序就大致的说完啦。