希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

基本思想

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列，分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录依次直接插入排序。

实现思路

  1. 选择一个增量序列 t1, t2, ……, tk，其中 ti > tj, tk = 1;
  2. 按增量序列个数 k，对序列进行 k 趟排序；
  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度；

动图演示

Sorting_shellsort_anim.gif

JavaScript 代码实现

  1. function shellSort(arr) {
  2.   const len = arr.length;
  3.   let temp;
  4.   let gap = 1;
  6.   while(gap < len / 3) { // 动态定义间隔序列
  7.       gap = gap * 3 + 1;
  8.   }
  10.   for (gap; gap > 0; gap = Math.floor(gap / 3)) {
  11.       for (let i = gap; i < len; i++) {
  12.         temp = arr[i];
  13.       for (let j = i - gap; j >= 0 && arr[j] > temp; j-= gap) {
  14.           arr[j + gap]= arr[j];
  15.       }
  16.       arr[j + gap] = temp;
  17.      }
  18.   }
  20.   return arr;
  21. }
  23. const arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
  24. console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

**