箱子排序与基数排序

局部排序

箱子排序 - binsort

proc bin_sort {item_list} {

  foreach score [$item cget -score-list] {
    dict set box_slots $score [list]
  }

  foreach item $item_list {
    set score [$item cget -score]
    dict lappend box_slots $score $item
  }

  dict for {score same_items} $box_slots {
    foreach item $same_items {
      lappend result $item
    }
  }

  return $result 
}

• binsort 是一种稳定排序 stable sort

基数排序 - radix sort

箱子排序的问题是可能需要的箱子的数目太多。对此的解决办法是「多做几遍」，每次不完全排序。

proc radix_sort {item_list score_idx} {
  if {$score_idx<0} {
    return $item_list
  }

  bin_sort $item_list [lambda {item score_idx}]
  foreach item $item_list {
    set score_list [$item cget -score-list]
    set score [lindex $score_list $score_idx]
    ...
  }

  incr score_idx -1
  return [radix_sort $result $score_idx]
}