希尔排序

希尔排序又叫递减增量排序，是一种更高效的插入排序的方法

• 时间复杂度（平均）：O(n ^ 1.3)
• 时间复杂度（最坏）：O(n ^ 2)
• 时间复杂度（最好）：O(n)
• 空间复杂度：O(1)
• 不稳定

算法

希尔排序基于插入排序的特点做了改进：

• 插入排序对几乎已排好的数组效率很高，几乎达到线性
• 但插入排序一般是低效的，因为每次只能将数据移动一位

希尔排序先确定一个分隔，将间隔相等的数据列为一组子序列，然后使用插入排序使子序列中数据有序

然后减小这个分隔，重新执行上述过程，得到一个新的由有序子序列组成的完整序列

直到分隔为1时，即子序列长度为1，整个序列当作表来处理

function shellSort(arr) {
	for (let gap = ~~(arr.length / 2); gap >= 1; gap = ~~(gap / 2)) {
		for (let i = gap; i < arr.length; i++) {
			for (j = i - gap; j >= 0; j -= gap) {
				if (arr[j] > arr[j + gap]) {
					[arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];
				}
			}
		}
	}
	return arr;
}