说下希尔排序的过程？希尔排序的时间复杂度和空间复杂度又是多少？

1959年Shell发明，第一个突破 O(n^2^) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。

插入排序

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

代码实现：

 
 
 
 
  
  
  
  function insertionSort(arr) {
  
  
  
      let n = arr.length;
  
  
  
      let preIndex, current;
  
  
  
      for (let i = 1; i < n; i++) {
  
  
  
          preIndex = i - 1;
  
  
  
          current = arr[i];
  
  
  
          while (preIndex >= 0 && arr[preIndex] > current) {
  
  
  
              arr[preIndex + 1] = arr[preIndex];
  
  
  
              preIndex--;
  
  
  
          }
  
  
  
          arr[preIndex + 1] = current;
  
  
  
      }
  
  
  
      return arr;
  
  
  
  }

插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

复杂度分析：

时间复杂度：O(n^2^)
空间复杂度：O(1)

希尔排序

回顾一下上面的插入排序：

第一趟插入排序后，我们得到的有效序列长度为 2
第二趟插入排序后，我们得到的有效序列长度为 3
...
直到这个序列有序

所以，如果序列足够乱的话，时间复杂度为 O(n^2^)

希尔排序又是如何优化的喃?

希尔排序又叫缩小增量排序，就是把数列进行分组(组内不停使用插入排序)，直至从宏观上看起来有序，最后插入排序起来就容易了(无须多次移位或交换)。

其中组的数量称为增量，显然的是，增量是不断递减的(直到增量为1)

那我们有是如何进行分组喃?

往往的：如果一个数列有 8 个元素，我们第一趟的增量是 4 ，第二趟的增量是 2 ，第三趟的增量是 1 。如果一个数列有 18 个元素，我们第一趟的增量是 9 ，第二趟的增量是 4 ，第三趟的增量是2 ，第四趟的增量是 1

很明显我们可以用一个序列来表示增量：n/2、(n/2)/2、...、1，每次增量都/2

例如：

 
 
 
 
  
  
  
  let arr = [4, 1, 5, 8, 7, 3]

排序前：

将该数组看成三组( Math.floor(arr.length/2) )，分别是：[4, 1] ， [5, 8] ， [7, 3]

第一趟排序：

对三组数据分别进行插入排序，因此我们三个数组得到的结果为：[1, 4] ， [5, 8] ， [3, 7]

此时数组是这样子的：[1, 4, 5, 8, 3, 7]

第二趟排序：

增量减少了，上面增量是 3 ，此时增量应该为 1 了，因此把 [1, 4, 5, 8, 3, 7] 看成一个数组(从宏观上是有序的了)，对其进行插入排序，直至有序

代码实现：

 
 
 
 
  
  
  
  function shellSort(arr) {
  
  
  
      let n = arr.length;
  
  
  
      for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
  
  
  
          for (let i = gap; i < n; i++) {
  
  
  
              let j = i;
  
  
  
              let current = arr[i];
  
  
  
              while (j - gap >= 0 && current < arr[j - gap]) {
  
  
  
                   arr[j] = arr[j - gap];
  
  
  
                   j = j - gap;
  
  
  
              }
  
  
  
              arr[j] = current;
  
  
  
          }
  
  
  
      }
  
  
  
      return arr;
  
  
  
  }

复杂度分析：

时间复杂度：O(nlogn)
空间复杂度：O(1)

名称栏目：说下希尔排序的过程？希尔排序的时间复杂度和空间复杂度又是多少？
网页地址：http://www.csdahua.cn/qtweb/news47/380897.html

网站建设、网络推广公司-快上网，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：快上网

成都快上网为您推荐相关内容