大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

每天一点算法-希尔排序 (Day6)

介绍

今天介绍第二种插入排序——希尔排序,该方法因D.L.Shell于1959年提出而得名,是第一个时间复杂度突破O(n^2)的排序算法,又叫缩小增量排序,在待排序数据量越大,希尔排序直接插入排序的优势就越加明显,但也是前面介绍几种算法中较难理解的一种。算法逻辑(升序为例):
初始时,有一个大小为 10 的无序序列:

1.在第一趟排序中,我们不妨设 gap1 = N / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组。
2.接下来,按照直接插入排序的方法对每个组进行排序。
在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组。
3.按照直接插入排序的方法对每个组进行排序。
4.在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组。
5.按照直接插入排序的方法对每个组进行排序。此时,排序已经结束。

希尔排序

例子

假设有一个待排序数组[77, 6, 37, 96, 34, 6, 14], js实现如下(升序):

function shellSort(arr) {
  var len = arr.length,
  temp,
  gap = 1;
  while(gap < len/5) { //动态定义间隔序列
    gap =gap*5+1;
  }
  for (gap; gap > 0; gap = Math.floor(gap/5)) {
    for (var i = gap; i < len; i++) {
      temp = arr[i];
      for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
        arr[j+gap] = arr[j];
      }
      arr[j+gap] = temp;
    }
  }
  return arr;
}
sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]

时间复杂度

时间复杂度为O(n^1.3)

感谢阅读!欢迎关注!持续更新中...