排序算法集锦系列之——希尔

缩小增量排序, 较为不稳定.

前置

---

时间复杂度

O(nlogn)

空间复杂度

O(1)

思路

---

思路一

• 动态定义增量step
• 内部进行插入排序

function shellSort(nums) {
  let step = nums.length;
  while (step > 1) {
    step = ~~(step / 3) + 1;
    for(let i = step; i < nums.length; i++) {
      const temp = nums[i];
      let j;
      for(j = i - step; j >= 0; j -= step) {
        if(nums[j] > temp) {
          nums[j + step] = nums[j];
        }else {
          break;
        }
      }
      nums[j + step] = temp;
    }
  }

  return nums;
}