• 希尔排序是简单插入排序的改进版，它又叫最小增量排序
  • 它与插入排序的不同之处在于，它会优先比较距离较远的元素
  • 其复杂度为 O(nlog n)

思路

  1. 根据序列长度算出步长，序列长度的一半即可
  2. 把距离等于步长的元素，分成一组，在组内进行插入排序
  3. 第二轮循环，步长减半，再次重复第二步分组，排序
  4. 直至步长为 1 ，最后进行一次插入排序，即可得到正序排列的序列

代码

  1. const shellSort = (list) => {
  2.   const len = list.length;
  3.   let gap = Math.floor(len / 2);
  5.   const insertionSort = (array, gap) => {
  6.     for (let i = gap; i < array.length; i++) {
  7.       for (let j = i - gap; j >= 0; j -= gap) {
  8.         if (array[j] > array[j + gap]) {
  9.           [array[j], array[j + gap]] = [array[j + gap], array[j]];
  10.         } else {
  11.           break;
  12.         }
  13.       }
  14.     }
  15.   };
  17.   for (gap; gap > 0; gap = Math.floor(gap / 2)) {
  18.     insertionSort(list, gap);
  19.   }
  21.   return list;
  22. };
  24. const list = [1, 4, 2, 6, 5, 8];
  25. console.log(shellSort(list));