希尔排序

原理解析

先将整个待排数组分割成若干个子数组（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个数组中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下效率是很高的，因此希尔排序在时间效率上较大提高。

范例演示

3 1 7 2 5 0 4 6

实现方式

function shellSort(arr) {
  var temp
  var len = arr.length
  for (var gap = len >> 1; gap > 0; gap = gap >>=1) {
    for (var i = gap; i < len; i++) {
      temp = arr[i]
      for( j = i - gap; j >=0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j]
      }
      arr[j + gap] = temp
    }
    console.log(arr)
  }
}

var arr = [3, 1, 7, 2, 5, 0, 4, 6]
shellSort(arr)
console.log(arr)

效率测试

下面我们测试排序性能。以下的代码中，randomArr 函数会生成一个随机数组， 数组长度默认是100， 最大值默认值是1000。 console.time 和 console.end 用来记录排序时间。

var arr = randomArr(10000, 100)
console.time('shellSort')
shellSort(arr)
console.timeEnd('shellSort')


function randomArr( arrLen = 100, maxValue = 1000 ) {
  let arr = []
  for(let i = 0; i < arrLen; i++) {
    arr[i] = Math.floor((maxValue+1)*Math.random())
  }
  return arr
}

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

经浏览器测试，对于长度为10000的数组，排序约需要2ms(100次平均值)， 对于长度为100000的数组，排序约需要 23.76ms(100次平均值)。

复杂度分析

时间复杂度为 O(nlog₂n)