恩，期待，期待。

晚上有好戏看咯。hoho

看看戏............

大家别忘记手机定时哦……非常期待

今晚、等喽、、

                                          决策树
 
决策树是用来证明下界的抽像概念。 决策树是一棵二叉树。每个节点表示在元素之间一组可能 的排序。 它与已经进行的比较一致。比较的结果是树的边。  
  
N个元素排序的决策树必然有 N！个树叶。 只使用元素间比较的任何排序算法在最坏情况下至少需要[log(N!)]次比较。 只使用元素间比较的任何排序算法需要进行O(NlogN)次比较.
 
证明: log(N!) = log(N (N-1).....(2) (1))  
  
              = log N + log (N-1) + ....+ log 2 + log 1  
  
              >=  N + log (N-1) + ....+ log N/2  
  
              >= N/2logN/2  
  
              >= N/2log - N/2  
   
              = O(NlogN)   
  
快速排序  合并排序  堆排序都能在 O(nlgn) 的时间内排序 n 个数。
而 线性时间的 排序算法：计数排序  基数排序  桶排序 都用非比较的一些操作来排序。
 
*******************************************************************************
 
[rofor专区]
 
题目:
  
对给定的 N个元素进行 递归形式 的快速排序，设子表的 第3大元素为 枢轴 (子表小于3个元素的, 以子表第一个元素为枢轴)。
求 元素交换 的次数。

首先吧，不同的划分算法，精确的比较次数应该是不一样的吧？比如国内经典的严蔚敏版本的划分算法，比较次数差不多在3n左右，但赋值次数很少（n），而国外经典的算法导论的划分算法的比较次数在2n左右，而赋值次数为3n（算一次交换需要三次赋值）。

我的意思是：在数据的结构不明的情况下，这样的（精确）讨论是没有意义的。要么是上界讨论（你已经讨论得很清楚了），要么是下界讨论（那涉及到别的计算模型）。单纯讨论精确的比较次数，恐怕无法有宏观上的作用。

另：目前CPU的瓶颈不是在于比较，而是在于取数和cache。理论上说，比较多一点，但是保存数字到内存少一点，在cache优秀的机器上，照样会很快。

再另：你出题，有点不公平，而且这个貌似是数学题，不怎么好直接做（除非rofer能牛到直接弄个函数出来，根据决策节点直接得出比较次数（那以后咱的A*估价函数就有东西照抄了）），第三，没有一个评测标准。

我的意见。飞雁之家160题（最新题），先AC者胜：http://www.

哇，那不是现在？

解题结束，谢谢合作。

LS：人家说了会发代码，那你也太亏了，人家自己实现一个trace_integer，修改其<运算符，然后用其调用标准的std::sort就完事了= =代码写起来贼简单（注意，人家只说过写代码，没承诺任何解释和注释）。

实在不行自己弄个quick_sort也简单的很阿……