希尔排序
概念
希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。
希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。
它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
过程
希尔排序就是按照一定的gap值，不断地对数组进行插入排序。不一样的希尔排序算法可能采用不一样的gap值。经典希尔算法的gap值为N/2, N/4, ...... 直到gap值为1，这里的N为数组的长度。
举个例子：
[8, 9, 1, 7, 2, 3, 5, 4, 6, 0] ,采取间隔 5 (gap = length/2)。创建一个位于 5 个位置间隔的所有值的虚拟子列表。下面这些值是 {8, 3}, {9, 5}, {1, 4}, {7, 6}, {2, 0}，我们这五个子序列分别进行插入排序。结果为 [3, 5, 1, 6, 0, 8, 9, 4, 7, 2] 。
接下来我们采取间隔 2（gap = 5/2），继续按位于2个间隔的所有值进行插入排序，这个间隔将产生以下两个子虚拟列表：[3, 1, 0, 9, 7] 与 [5, 6, 8, 4, 2]，都进行插入排序，结果为 [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]。
最后我们采取间隔 1 (gap = 2/2)，也就是对整个序列进行插入排序（此时的序列已经基本有序了），结果为 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]。
实现
/**e
* @description: 希尔排序
* @param {Array}
*/
function shellSort(arr) {
let gap = arr.length
while(gap > 1) {
gap = Math.floor(gap/2)
for (let i = 1; i < arr.length; i++) {
let temp = arr[i]
let j = i - gap
for ( ; j >= 0 && temp < arr[j]; j = j-gap) {
arr[j+gap] = arr[j]
}
arr[j+gap] = temp
}
}
}
shellSort([8, 9, 1, 7, 2, 3, 5, 4, 6, 0])
希尔排序与直接插入排序区别
希尔排序是插入排序的优化：
1.当数组长度很大时，使用插入排序有个弊端，就是如果最小值排在很末端的时候，插入排序需要从末端开始，逐个往前比较到第一个位置，很低效。而希尔排序通过分组的方式，直接让前端跟末端的元素进行比较，解决了插入排序的这个弊端。
2.当一开始 增量n 很大的时候，每一个子数组的元素很少，所以对每个子数组用插入排序进行内部排序是很高效的；而后随着增量n不断减小，这个数组是越来越有序的，此时使用插入排序也是很有利的。