Archive for the ‘算法’ Category
线性时间排序
前面说的算法都是基于输入元素的比较，即所谓的比较排序。而任意一个比较排序算法在最坏情况下，都需要做Ω(nlgn) 次的比较。因此堆排序和合并排序都是渐进最优的比较排序算法。具体证明用到决策树模型。参见这里。
本文讨论的则是三种以线性时间运行的非比较排序算法：计数排序、基数排序和桶排序。
排序算法整理（三）
堆排序和快速排序。
排序算法整理（二）
关于冒泡排序和选择排序
排序算法整理（一）
最近面试遇到好多关于排序算法的题目。算法没系统的学过，只在数据结构中有一点点涉及。就趁这机会复习下排序算法。
@
