排序 - 熵减的策略方法

排序用于查找。

为了讨论过程中的一致性，本文设定：

• 从小到大排序
• 通过交换元素位置实现排序
• 已排序的部分位于左边

foreach value {3 7 5 2 6 1 4 8} {
  box $value
}

比较和交换

排序涉及两个基本操作：

1. 比较大小
2. 交换位置

用 Tcl 程序定义如下

proc list-less {list i j} {
  # 比较大小
  if { [lindex $list $i] < [lindex $list $j] } {
    return true
  } else {
    return false
  }
}

proc list-swap {&list i j} {
  # 交换位置
  upvar ${&list} list
  set tmp [lindex $list $i]
  lset list $i [lindex $list $j]
  lset list $j $tmp
}

选择排序

• 左侧已排序
• 右侧未排序
  1. 从右侧选出最小的
  2. 和右侧最左边的位置交换
• 思路是选出全局最小的

foreach value {1 2 3 4} {
  box $value -fill #cfc
}

box "6" -fill yellow

foreach value {5 7 8} {
  box $value -fill #fcc
}

Tcl 代码如下：

proc select-sort {list n} {
  for {set i 0} {$i<$n} {incr i} {
    set idx [select-min $list $i $n]     ;# 选择
    list-swap &list $i $idx              ;# 交换
  }
}

proc select-min {list start stop} {
  for {
    set min_idx $start
    incr start  
  } {$start<$stop} {incr start} {
    if {[list-less $start $min_idx]} {
      set min_idx $start
    }
  }
  return $min_idx
}

冒泡排序

• 左侧已排序
• 对于右边的未排序部分
  1. 从右至左
  2. 比较相邻的两个数字
  3. 把较小的交换到左边
  4. 犹如气泡从水底上浮到水面
• 思路是发现局部最小后，移动位置

foreach value {1 2 3 4} {
  box $value -fill #cfc
}

box "7" -fill yellow

foreach value {5 6 8} {
  box $value -fill #fcc
}

Tcl 代码如下：

proc bubble-sort {list n} {
  set end [expr {$n-1}]
  for {set i 0} {$i<$n} {incr i} {
    list-bubble &list $i $end             ;# 冒泡
  }
}

proc list-bubble {&list start end} {
  upvar ${&list} list
  for {} {$end>$start} {incr end -1} {
    if { [list-less $list $end $end-1] } {
      list-swap &list $end $end-1     ;# 交换
    }
  }
}

插入排序

• 左侧已排序
• 对于右侧的未排序部分
• 选择第一个元素
• 插入到左侧已排序部分中适当位置
• 插入过程可以看作是可以提前终止的「冒泡」

foreach value {2 3 5 7} {
  box $value -fill #cfc
}

box "6" -fill yellow

foreach value {1 4 8} {
  box $value -fill #fcc
}

Tcl 代码如下：

proc insert-sort {*list} {
  for {set i 1} {$i<n} {incr i} {
    insert-bubble &list 0 $i
  }
}

proc insert-bubble {&list start end} {
  upvar ${&list} list
  for {} {$end>$start} {incr end -1} {
    if { [list-less $list $end $end-1] } {
      list-swap &list $end $end-1     ;# 交换
    } else {
      return                          ;# 提前终止
    }
  }
}