排序 - 选择排序 / Selection Sort

选择排序是最自然地排序思路。

不就是排序嘛，每次挑出最小的那个，排到前面去。就是这么简单。

Selection Sort 循环

proc selection-sort {list n} {
  for {set i 0} {$i<$n} {incr i} {
    ;# 选出最小的，交换到第一个位置
    select-min &list $i $n
  }
}

选出最小的

proc select-min {list start stop} {
  upvar ${&list} list

  set min_index $start
  set min_value [lindex $list $start]

  list-foreach {value index} $list $start $stop {
    if {$value < $min_value} {
      set min_value $value
      set min_index $index
    }
  }

  list-swap &list $start $min_index
}

Selection Sort 递归

递归描述，更有利于理解算法的思路。

proc selection-sort-recur {list start stop} {
  if {$start>=$stop} {
    return $list
  }

  #% 基本操作
  set list [select-min $list $start $stop]

  selection-sort-recur $list [incr start] $stop
}

在 Tcl 语言里，可以借助 tailcall 命令避免栈溢出（Stack Overflow）。

Less Writing - 更少的写操作

选择排序的一个好处是需要的写操作比较少。

相对于 Insertion Sort 或者 Bubble Sort 来说，Selection Sort 每个会回选出最小值之后，只需要一次交换操作 —— 两次写入操作。

很多时候，计算机的写操作可能会需要更多的时间。

Cycle Sort 是理论上写入操作最少的排序算法。

Stable Selection Sort

对于排序算法来说，所谓的 stable 指的是排序后相同的值的相对顺序不便。

对于上面的选择排序实现来说，swap 的步骤有可能导致相对顺序改变。

因此，如果需要一个 Stable Selection Sort，需要用 list-shift 来进行位置调整。

同时选出最小的和最大的

• cocktail sort - double selection sort

proc cocktail-sort {list n} {
  for {set i 0} {$i<$n} {incr i ; incr n -1} {
    ;# 选出最小的，交换到第一个位置
    select-min-max &list $i $n
  }
}

bingo sort - 利用重复的最小值

如果序列中有很多重复项，那么也许可以在查找最小值的过程中利用这个信息。

问题的窍门在于，在当前查找最小值的过程中，当前回合的最小值还不确定，但上一回合的最小值是确定的。因此如果遇到了和上一回合的最小值一样的值，可以直接判定它就是最小值。

proc select-min-bingo {list start stop} {
  upvar ${&list} list

  set min_index $start
  set min_value [lindex $list $start]
  set min_prev  [lindex $list $start-1]

  list-foreach {value index} $list $start $stop {
    if {$value == $min_prev} {
        #% 发现最小值
        list-swap &list $start $index
        incr start
    } elseif {$value < $min_value} {
      set min_value $value
      set min_index $index
    }
  }

  list-swap &list $start $min_index
}

上面的代码不是局部最优的。可以通过改变比较操作的顺序进一步局部优化。

Heap Sort 堆排序

选择排序的关键是选择最小或最大值。

如果元素序列是按照特定的方式排列的，是可以加速选择过程的。

堆排序就是这样一种排序算法。可以把时间复杂度从 n^2 变为 n*log(n)