前言
经典的排序算法，很多人都听过，很多人也许用过，但是也有很多人，听过没见过。为什么呢？现在我们有了越来越多的框架、依赖包，我们将能用到排序的实际场景，作为业务将其封装成了函数，所以，一些人只知函数而不知其运行逻辑。
基于以上，为了让自己更好的理解函数运行逻辑，整理了一些基本排序的方法的运行规则，以及部分个人理解，希望能给大家一些帮助。
本文将讲述希尔排序。希尔排序简单来讲就是拆分数组进行分别排序；
希尔排序
希尔排序是一种基于插入排序的快速排序算法，也称为缩小增量排序。简单插入排序对于大规模乱序数组很慢，因为元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插入排序，同时该算法是冲破O(n2)的第一批算法之一。
希尔排序实现原理
- 把数组按照一定的增量分组，对每组使用直接插入排序算法排序，希尔建议的间距是N/2，每一趟排序分成两半，也就是说，对于N=10的数组，增量间隔序列为5、2、1；
- 然后缩小增量继续分组排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数组被分成一组，再次排序，就可以完成整个数组的排序；
代码
function shellSort(array) {
//每次向下得到一半的增量
for (let gap = Math.floor(array.length / 2); gap > 0; gap = Math.floor(gap / 2)) {
//每个分组进行插入排序
for (let i = gap; i < array.length; i++) {
let j = i;
let tmp = array[j];
// 如果同一组中 前数大于后数，则交换他们
if (array[j] < array[j - gap]) {
while (j - gap >= 0 && array[j - gap] > tmp) {
array[j] = array[j - gap];
j = j - gap;
}
array[j] = tmp;
}
}
}
console.log('shellSort result', array);
}
shellSort([2, 4, 7, 9, 0, 1, 2, 3, 5, 6, 8]);
返回值
复杂度
时间复杂度：
- 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
- 最坏情况：O(nlog2n)。
- 渐进时间复杂度（平均时间复杂度）：O(nlog2n)
空间复杂度：O(2n)
寄语
希尔排序整体上来说是最不稳定的，但是在最好情况下，是很好的一种排序方法！
