javascript算法排序之希尔排序

​
​

活动地址：CSDN21天学习挑战赛

前言

经典的排序算法，很多人都听过，很多人也许用过，但是也有很多人，听过没见过。为什么呢？现在我们有了越来越多的框架、依赖包，我们将能用到排序的实际场景，作为业务将其封装成了函数，所以，一些人只知函数而不知其运行逻辑。

基于以上，为了让自己更好的理解函数运行逻辑，整理了一些基本排序的方法的运行规则，以及部分个人理解，希望能给大家一些帮助。

本文将讲述希尔排序。希尔排序简单来讲就是拆分数组进行分别排序；

希尔排序

希尔排序是一种基于插入排序的快速排序算法，也称为缩小增量排序。简单插入排序对于大规模乱序数组很慢，因为元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插入排序，同时该算法是冲破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]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

返回值

复杂度

时间复杂度：

• 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
• 最坏情况：O(nlog2n)。
• 渐进时间复杂度（平均时间复杂度）：O(nlog2n)

空间复杂度：O(2n)

寄语

希尔排序整体上来说是最不稳定的，但是在最好情况下，是很好的一种排序方法！利弊同样明显。慎用！