希尔排序算法

算法简介

先递归的分解数列，再合并数列（分治思想的典型应用）

基本思想与过程：先递归的分解数列，再合并数列（分治思想的典型应用）

  1. 将一个数组拆成 A、B 两个小组，两个小组继续拆，直到每个小组只有一个元素为止。

  2. 按照拆分过程逐步合并小组，由于各小组初始只有一个元素，可以看做小组内部是有序的，合并小组可以被看做是合并两个有序数组的过程。

  3. 对左右两个小数列重复第二步，直至各区间只有 1 个数。

下面对数组【42,20,17,13,28,14,23,15】进行归并排序，模拟排序过程如下：

第一步：拆分数组，一共需要拆分三次（logN）；

第一次拆成【42,20,17,13】，【28,14,23,15】，

第二次拆成【42,20】，【17,13】，【28,14】，【23,15】，、

第三次拆成【42】，【20】，【17】，【13】，【28】，【14】，【23】，【15】；

第二步：逐步归并数组，采用合并两个有序数组的方法，每一步其算法复杂度基本接近于 O(N)

第一次归并为【20,42】，【13,17】，【14,28】，【15,23】

第二次归并为【13,17,20,42】，【14,15,23,28】，

第三次归并为【13, 14, 15, 17, 20, 23, 28, 42】

代码实现：

  1. 辅助函数：合并两个有序数组的方法 merger(left, right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const merger = (left, right) => {
    const n = left && left.length;
    const m = right && right.length;
    let backs = [];
    let i = 0;
    let j = 0;
    while(i < n && j < m) {
      if (left[i] < right[j]) {
        backs.push(left[i++])
      } else {
        backs.push(right[j++])
      }
    }
    while(i < n) {
      backs.push(left[i++])
    }
    while(j < m) {
      backs.push(right[j++])
    }
    return backs;
  }
  1. 归并程序为：
1
2
3
4
5
6
7
const mergeSort = (arr) => {
    if(arr.length == 1) return arr
    var mid = Math.floor(arr.length/2)
    var left = arr.slice(0,mid)
    var right = arr.slice(mid)
    return merger(mergeSort(left), mergeSort(right))
}

复杂度

时间复杂度（平均）：O（nlog2 n）
时间复杂度（最坏）：O（nlog2 n）
时间复杂度（最好）：O（nlog2 n）
空间复杂度（）：O（n）
稳定性：稳定

总结

先递归的分解数列，再合并数列（分治思想的典型应用）