#希尔排序

function sortArray(nums: number[]): number[] {
  if (nums.length <= 1) {
    return nums
  }

  // 使用间隔nums.length/2，并且每次循环都将间隔/2
  for (
    let gap = Math.floor(nums.length / 2);
    gap > 0;
    gap = Math.floor(gap / 2)
  ) {
    // 将插入排序中的在有序数组中逐1比较改为逐间隔比较
    for (let i = gap; i < nums.length; i++) {
      for (let j = i; j >= gap && nums[j - gap] > nums[j]; j = j - gap) {
        ;[nums[j - gap], nums[j]] = [nums[j], nums[j - gap]]
      }
    }
  }

  return nums
}