# 希尔排序

TIP

希尔排序(Shell Sort)是希尔(Donald Shell)于 1959 年提出的一种排序算法,也是第一个突破 O(N²)的排序算法。希尔排序是经过改进之后的一个更加高效的插入排序版本,它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

# 算法描述

  • 步骤 1:计算希尔增量序列
    1. 初始增量 gap = length / 2
    2. 缩小增量继续以 gap = gap/2 的方式
    3. 最后得到一个增量序列 {n/2, (n/2)/2 … 1}
  • 步骤 2:按增量序列个数 k,对序列进行分组
  • 步骤 3:对每组内部进行插入排序
  • 步骤 4:最后增量序列为 1 的时候,对整体进行一次插入排序,就得到最终排序数组

# 静图演示

sort

# 动图演示

sort

# 代码编写

// 希尔排序
function shellSort(arr) {
	// 1. 获取数组长度
	var length = arr.length

	// 2.根据长度计算增量(向下取整)
	var gap = Math.floor(length / 2)

	// 3. while 循环,让增量不断变小,进而分组,然后内部排序调整位置
	while (gap >= 1) {
		// 4. 以gap为间隔,进行分组,对分组进行插入排序
		for (var i = gap; i < length; i++) {
			// 4.1 保存临时变量
			var tmp = arr[i]
			var j = i
			// 4.2 内层循环: 插入排序
			while (j > gap - 1 && arr[j - gap] > tmp) {
				arr[j] = arr[j - gap]
				j -= gap
			}
			// 4.3 将j的位置元素赋值tmp
			arr[j] = tmp
		}

		// 5. 重新计算gap
		gap = Math.floor(gap / 2)
	}

	// 6. 返回数组
	return arr
}

# 代码解析

文字说明

  • 第一步:获取数组长度
  • 第二步:计算第一次的间隔, 按照希尔提出的间隔实现(gap = length / 2)
  • 第三步:增量不断变小, 大于 0 就继续改变增量
  • 第四步:编写插入排序:
    1. 保存临时变量, j 位置从 i 开始, 保存该位置的值到变量 tmp 中
    2. 内层循环, j > gap - 1 并且 tmp 大于 arr[j - gap], 那么就进行复制
    3. 将 j 位置设置为变量 tmp
  • 第五步:每次 while 循环后都重新计算新的间隔

图解分析

sort

# 代码测试

// 测试希尔排序
var arr = [3, 6, 4, 2, 11, 10, 5]
console.log(shellSort(arr).join("-"))
// 2-3-4-5-6-10-11

# 排序效率

  • 希尔排序的效率和增量有直接关系,即使使用原稿中的增量效率都高于简单排序
  • 但是经过统计, 希尔排序使用原始增量, 最坏的情况下时间复杂度为 O(N²), 通常情况下都要好于 O(N²)