希尔排序也称为“缩小增量排序”，它的基本原理如下：首先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，等整个待排序列“基本有序”后，最终再对所有元素进行一次直接插入排序。
function shellSort(arr) {
let length = arr.length, gap = 0, temp;
while (gap < length / 5) {gap = gap \* 5 + 1; }
for (; gap > 0; gap =Math.floor(gap / 5)) {
for (let i = gap; i < length; i++) {
temp = arr[i];
for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
{ arr[j + gap] = arr[j];}
}
arr[j + gap] = temp;
}
return arr;
}
最佳情况： T(n) = O(nlog2n)；最差情况： T(n) = O(nlog2n)；平均： T(n) = O(nlogn)。