原理

希尔排序是插入排序的改进版本。
项目中用的比较少,不稳

  1. 先设置一个间隔(gap),以视为一组。
  2. 当这个间隔的所有组全排序好后,减少间隔,重复1.
  3. 最后以间隔为1,在排序。(其实就是最后执行次插入排序,插入排序就是间隔1的希尔排序)
    注:间隔越大,交换次数越小! 间隔越小,交换次数越多

通常间隔以h或者gap表示

举例说明

如:需要对以下数组进行排序

const arr = [8, 5, 6, 3, 11, 2, 9, 15, 13, 1, 14, 6, 9, 10]

假设间隔(gap)为4,如下图,相同颜色的为一组,执行插入排序。

希尔排序1.png

既然每个数(除去最前面的没有可比较的数以外)都会执行插入排序。那么我们就可以直接使用普通的插入排序方式来实现,只需要将默认的间隔1改为对应的gap

代码实现

我们先来看看普通的插入排序

  for (let i = 1; i < arr.length; i++) { // 以1(第0个数前面没有需要比较的)开始,直到数组跑完
    for (let k = i ; k > 0; k--) {  // 依次与前面的进行比较。如 i=1时,依次与i-1比。i>0是因为i=0时,前面没有数比较了,所以不需要
      if (arr[k] < arr[k - 1]) {
        // 交换 k和 k-1
      } else {
          break;
        }
    }
  }

前面我们也说过,插入排序也可以看做是一个间隔为1的希尔排序

// 一次间隔的排序
function shell_sort_gap(arr, gap) {
  // 普通的插入排序是以,1开始的。而希尔排序,既然以间隔分组,就相当于 0-第一个间隔是一组的,那就是以间隔排序
  for (let i = gap; i < arr.length; i++) { // 以gap开始
    for (let k = i; k > gap - 1; k -= gap) { // 依次与前面的进行比较,每次差距为gap。这里gap-1,是因为gap肯定是最小的可比较数,最前面的那几个数就不要再遍历比较了。
      if (arr[k] < arr[k - gap]) {
        // 交换 k和 k-1
        array_swap(arr, k, k - gap)
      } else {
        break;
      }
    }
  }
}

上面只是间隔为某一个数时的排序,后面需要减少间隔,直到间隔为1。
for (let gap = 4; gap > 0;) { // 这里的4,是我主观意识上取的值

shell_sort_gap(arr, gap)
gap = Math.floor(gap / 2) // 向下取整,如果是其他语言,gap类型为int,就不需要Math.floor了,JS需要不然会有小数

}

上面初次间隔的值,是主观意识上给的,对于算法来说肯定是不合适的。
因此我们改成,默认为数组的一半,然后依次将间隔/2。

  for (let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)) { 
    shell_sort_gap(arr, gap)
  }

但后续很多人发现,这种除以2的方式效率(shell发现的)不是最高的(Knuth(K不发音)发现的)。(还有一些其他的算法)

h = 1
h = 3*h+1
//当h=3h+1时,效率更高!h就是gap,通常算法里默认就是h

因此我们先以1带入h计算出最适合的h,在以公示倒推排序

function shell_sort(arr) {    
  if (arr.length < 2) {
    return
  }
  // 计算最优的gap
  let h = 1
  while (h <= arr.length / 3) { //如果大于1/3了,就超过数组长度了。因此需要小于等于1/3
    h = 3 * h + 1
  }
  for (let gap = Math.floor(h); gap > 0; gap = Math.floor((gap - 1) / 3)) { // 再以倒推的方式排序
    shell_sort_gap(arr, gap)
  }
}

由此可见,不同gap减少方式,会导致效率不同,因此希尔排序的时间复杂度不尽相同,普遍认为是O(n的1.3次方)。

标签: none

添加新评论