排序 - 希尔排序 Shell Sort

Shell Sort 可以看作改进版的 Insertion Sort。

希尔排序

插入排序的问题在于，如果右侧的数据全局来看比较小的话，insert-bubble 过程中不能尽早地「提前终止」。 这种情况也可以认为是较大的数据所在的位置比较靠近左边。 如果可以尽早地把那些较大的数据移动到右边的话，可以促使「提前终止」的尽早发生。

这可以通过尽早比较左侧的较大数据和右侧的较小数据，并交换它们的位置来实现。

以一定的间隔抽样检查，是很自然的思路。在此思路基础上，可以把原数组看作是多个子数组的组合。

分别对这多个子数组进行排序，之后整个数组的布局会更有利于整个数组的排序。

希尔排序巧妙地利用逐步减小间隔的办法，把子数组的划分和排序，以及整个数组的排序，统一在一起。希尔排序是基于插入排序的——插入排序有可以提前终止的特性。

proc insert-sort-step {*list step} {
  for {set i 0} {($i+$step)<n} {incr i $step} {
    insert-bubble &list 0 $i+$step $step
  }
}

proc insert-bubble {&list start end} {
  upvar ${&list} list
  for {
    set prev [expr $end-$step]     ;# 间隔序列
  } {$prev>$start} {
    incr prev -$step
    incr end  -$step
  } {
    if { [lindex $list $end] < [lindex $list $prev] } {
      list-swap &list $prev $end     ;# 交换
    } else {
      return                         ;# 提前终止
    }
  }
}