美文网首页
排序算法4-希尔排序

排序算法4-希尔排序

作者: 小杰66 | 来源:发表于2021-04-17 19:14 被阅读0次

    希尔排序

    • 平均时间复杂度:O(nlogn)
    • 最好情况:O(nlog^2n)
    • 最坏情况:O(nlog^2n)
    • 空间复杂度:O(1)
    • 排序方式:In-place
    • 稳定性:不稳定

    算法步骤:
    1.先取一个小于待排序数列长度n的整数d1作为第一个增量,将所有距离为d1的倍数的记录放在同一个组中。(一般的初次取序列的一半为增量,以后每次减半,直到增量为1。)
    2.在各组内进行插入排序;
    3.取第二个增量d2<d1重复上述的分组和排序,直至增量为1,即所有记录放在同一组中进行插入排序。

    例如待排序数组为: [1, 10, 3, 2, 5, 8, 4, 7, 9, 6]
    1.第一次增量设为数组长度的一半即5, 数组被分为五组分别为[1,8]/[10,4]/[3,7]/[2,9]/[5,6]
    2.然后对每组做插入排序操作,操作后的数组为[1, 4, 3, 2, 5, 8, 10, 7, 9, 6]
    3.第二次增量设为之前增量的一半取整即2,数组被分为两组分别为[1,3,5,10,9]/[4,2,8,7,6]
    4.然后对每组做插入排序操作,操作后的数组为[1, 2, 3, 4, 5, 6, 9, 7, 10, 8]
    5.第三次增量再次设为之前增量的一半即1,数组只分为一组,排序后结束。

    function shellSort(arr) {
      let len = arr.length;
      let temp,
        gap = len;
      while ((gap >>= 1)) {
        for (let i = gap; i < len; i++) {
          temp = arr[i];
          let j = i;
          for (; j >= gap && arr[j - gap] > temp; j -= gap) {
            arr[j] = arr[j - gap];
          }
          arr[j] = temp;
        }
      }
    }
    

    改进
    希尔排序的优化主要在增量的选择,上面的实现取了2,一般都是取2或3。 至于最优值是多少貌似仍是一个数学难题。

    相关文章

      网友评论

          本文标题:排序算法4-希尔排序

          本文链接:https://www.haomeiwen.com/subject/bckhlltx.html