1959年Shell发明，第一个突破 O(n^2^) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。
插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
代码实现：
复制
![[[429028]]](https://s4.51cto.com/oss/202110/15/62026af522060c4d8c07bc841bb8643a.jpg){kind=link}
function insertionSort(arr) { let n = arr.length; let preIndex, current; for (let i = 1; i < n; i++) { preIndex = i - 1; current = arr[i]; while (preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current; } return arr; }
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
时间复杂度：O(n^2^)
空间复杂度：O(1)
回顾一下上面的插入排序：
第一趟插入排序后，我们得到的有效序列长度为 2
第二趟插入排序后，我们得到的有效序列长度为 3
...
直到这个序列有序
所以，如果序列足够乱的话，时间复杂度为 O(n^2^)
希尔排序又是如何优化的喃?
希尔排序又叫缩小增量排序，就是把数列进行分组(组内不停使用插入排序)，直至从宏观上看起来有序，最后插入排序起来就容易了(无须多次移位或交换)。
其中组的数量称为 增量 ，显然的是，增量是不断递减的(直到增量为1)
那我们有是如何进行分组喃?
往往的： 如果一个数列有 8 个元素，我们第一趟的增量是 4 ，第二趟的增量是 2 ，第三趟的增量是 1 。如果一个数列有 18 个元素，我们第一趟的增量是 9 ，第二趟的增量是 4 ，第三趟的增量是2 ，第四趟的增量是 1
很明显我们可以用一个序列来表示增量：n/2、(n/2)/2、...、1，每次增量都/2
例如：
复制
let arr = [4, 1, 5, 8, 7, 3]
1.
排序前：
将该数组看成三组( Math.floor(arr.length/2) )，分别是：[4, 1] ， [5, 8] ， [7, 3]
第一趟排序：
对三组数据分别进行插入排序，因此我们三个数组得到的结果为：[1, 4] ， [5, 8] ， [3, 7]
此时数组是这样子的：[1, 4, 5, 8, 3, 7]
第二趟排序：
增量减少了，上面增量是 3 ，此时增量应该为 1 了，因此把 [1, 4, 5, 8, 3, 7] 看成一个数组(从宏观上是有序的了)，对其进行插入排序，直至有序
代码实现：
复制
function shellSort(arr) { let n = arr.length; for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) { for (let i = gap; i < n; i++) { let j = i; let current = arr[i]; while (j - gap >= 0 && current < arr[j - gap]) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; } } return arr; }
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
复杂度分析：
时间复杂度：O(nlogn)
空间复杂度：O(1)