lecture：沈孝钧 record：孙相国 time：2017/06/07

1. 排序

n−1+⌈lgn⌉ 对排序 基数排序 counting排序 tournament sorting

决策树找到没有重复的数。 不可能有线性时间得到频率最高的数字，否则的话，用线性时间可以找到一组数列中的频率最高的数字，如果不是1，那么就说明这组数列有重复的数字。然而我们之前证明，这个过程不可能超过nlgn