我
希尔排序
希尔排序的基本思想是把数组按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元 素越来越多，当增量减至 1 时，整个数组恰被分成一组，算法便终止。
代码实现：
js
function hillSort(array) {
let length = array.length;
// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
if (!Array.isArray(array) || length <= 1) return;
// 第一层确定增量的大小，每次增量的大小减半
for (let gap = parseInt(length >> 1); gap >= 1; gap = parseInt(gap >> 1)) {
// 对每个分组使用插入排序，相当于将插入排序的1换成了 n
for (let i = gap; i < length; i++) {
let temp = array[i];
let j = i;
while (j - gap >= 0 && array[j - gap] > temp) {
array[j] = array[j - gap];
j -= gap;
}
array[j] = temp;
}
}
return array;
}希尔排序是利用了插入排序对于已排序序列排序效果最好的特点，在一开始序列为无序序列时，将序列分为多个小的分组进行基数排序，由于排序基数小，每次基数排序的效果较好，然后在逐步增大增量，将分组的大小增大，由于每一次都是基于上一次排序后的结果，所以每一次都可以看做是一个基本排序的序列，所以能够最大化插入排序的优点。
简单来说就是，由于开始时每组只有很少整数，所以排序很快。之后每组含有的整数越来越多，但是由于这些数也越来越有序，所以排序速度也很快。
希尔排序的时间复杂度根据选择的增量序列不同而不同，但总的来说时间复杂度是小于 O(n^2) 的。
插入排序是一个稳定排序，但是在希尔排序中，由于相同的元素可能在不同的分组中，所以可能会造成相同元素位置的变化，所以希尔排序是一个不稳定的排序。
希尔排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n^s) ，空间复杂度为 O(1) ，不是稳定排序。