快速排序 Quick Sort - 向着正确的方向前进

快速排序的基本思路是如果可以把序列划分成两半，使得其中的一半总是比另一半大，那么再分别对那两半递归进行类似的划分，最终就可以实现完全有序。

proc quick-sort {&vector low high} {
  set pivot [quick-sort-pivot $vector]
  set mid   [quick-sort-partition $vector $low $high $pivot]
  quick-sort $vector $low   $mid-1
  quick-sort $vector $mid+1 $high
}

Quick Sort 可以分为 3 个基本步骤

1. 选定基准点 Pivot
2. 以基点值为标准，划分成两半
3. 分别对左右两半再次递归划分

可以看出，可以局部调整的就是如何选择基准点和如何实现划分两个步骤。

# 5  3 7 2 6 1 4 8
box 5 -fill yellow
box 3 -fill lightgreen

foreach value {7 2 6 1 4} {
  box $value
}
box 8 -fill pink


# down
#
# foreach value {5 3 7 2 6 1 4 8} {
# switch $value {
#    5 {box $value -fill yellow}
#    7 {box $value -fill lightgreen}
#   4 {box $value -fill pink}
#    default {box $value}
#  }
# }

局部有序，曲中求直

选择排序，插入排序这类方法从排序的一开始，你就可以看到预期的效果。最终想要的结果已经明确显现，剩下的只是时间问题。

快速排序则不然，只从旁观者角度来看，即使已经做了不少工作（经过了好几个回合的迭代），整体结果看起来似乎仍然距离最终目标很遥远。

如果旁观者就是决策者，又不明其理的话，很可能会在中途丧失信心，或者放弃，或者转而寻找其它方法。

神奇的是，这个时候很可能离最终目标已经非常近了。

方向很重要

快速排序这种表面上乍看其来没有效果的方法，有点“方向比努力”重要这种含义。

初看起来，没啥明显效果，但我们知道，情况再改善。就是这一点点的改善，看起来不起眼，积累起来，却很快可以实现量变到质变的转换。

以基准点为标准分成两半

就分成两半的思路而言，可以用 Tcl 表示如下。

proc quick-sort-partition {&vector low high pivot} {
  set pivot_value [lindex $vector $pivot]

  set smaller [list]
  set bigger [list]

  list-foreach $vector $low $high {
    if {$value<$pivot} {
       lappend smaller $value
    } else {
       lappend bigger $value
    }
  }

  set vector [concat $smaller $bigger]
  set mid [length $smaller]

  return $mid
}

上面的划分操作是重新创建了一个新的序列。

Quick Sort 本身是一种 in-place 排序。因此实践中是通过交换实现局部有序的。

原地交换

面对一组随机的数据，随便选择哪个基准点，可能差别都不大。如果不知道怎么选最好，那就选最近的排在第一个位置的这名同学吧。

proc quick-sort-partition {&vector low high pivot} {
  set pivot $low
  set pivot_value [lindex $vector $pivot]
  incr low

  while {$low<$high} {
    while {$low < $high} {
      if {[llinex $vector $low]>=$pivot_value} {
        break
      }
      incr low
    }

    while {$high > $low} {
      if {[llinex $vector $high]<$pivot_value} {
        break
      }
      decr high
    }

    if {$low<$high} {
      list-swap $vector $low $high
      incr low ; decr high
      continue
    } else {
      set mid $low
      if {$pivot_value>[lindex $vector $mid]} {
        list-swap $vector $pivot $mid
      }
      break
    }
  }

  return $mid
}