跳到主要内容

希尔排序

希尔排序如何工作？​

  • 思路: 插入排序的改进, 先让数组"基本有序", 再做间隔为 1 的插入排序;
  • 步骤: 取间隔 gap, 把数组拆成若干间隔为 gap 的子序列, 分别做插入排序;
  • 迭代: 不断缩小 gap, 重复上一步;
  • 终止: gap 缩到 1 时执行最后一次插入排序, 得到有序数组;

希尔排序如何实现？​

function shellSort(nums: number[]): void {
  let gap = Math.floor(nums.length / 2);
  while (gap > 0) {
    for (let i = gap; i < nums.length; i++) {
      const base = nums[i];
      let j = i - gap;
      while (j >= 0 && nums[j] > base) {
        nums[j + gap] = nums[j];
        j -= gap;
      }
      nums[j + gap] = base;
    }
    gap = Math.floor(gap / 2);
  }
}

希尔排序的特性是什么？​

  • 时间复杂度: 随间隔序列而变, 介于 O(n log n) 与 O(n^2) 之间;
  • 上面 gap 折半的实现在最坏情况下为 O(n^2), 但实现简单;
  • 空间复杂度: O(1);
  • 稳定性: 非稳定排序, 相等元素可能在不同子序列间换位;