我们先提出几个问题. 

Problem 1.1
试用最快的方法找到给定五个两两不同的数的中位数.

Problem 2.1
试求基于比较的排序的时间复杂度的下确界.

Problem 3.1
现在有一个序列, 其只包含0, 1, 2三种元素. 那么, 在只允许额外申请常数空间的前提下, 试求最快的对这个序列排序的方法. 

对Problem 1.1的思考有助于我们引入比较, 排列, 和排序的概念. 对于Problem 2.1来说, 我们将一般性地探讨一下基于比较的排序的原理和复杂度分析, 从而在得出结论的同时给出详细的说明.

我们将在本文的最后部分解决Problem 3.1这一个特殊的排序问题. 在此基础上, 我们将探讨一下不基于比较的排序的原理和复杂度分析, 以及适用范围.

我的博客的上一个系列, 即"算法漫谈"系列, 于两年前的夏天已经完结. 此后繁忙于诸事, 亦无暇打理博客空间. 偶有读者反馈一些问题, 我便逐个修复. 

然而近两年, 助教工作已成为我工作中不可少的一部分. 我助教的课程涵盖Programming Languages (内容主要涵盖编程语言的类型化定义和函数式类型方法, 区别于'学习一门编程语言'的课程), 计算机理论, 编译原理, 和算法, 受众也从本科生, 硕士生涵盖到博士生. 这时我便有一种想法, 即把助教工作中的一些知识点和自己对数据结构与算法的认识结合起来, 写一些东西放在博客上.

加之近日, 身边有不少同学和朋友也在频繁更新博客. 我在浏览他们的文章同时, 再次感到书写博客对于梳理一些心情杂感, 或是强化对一些知识点的认识, 亦或是与身边的同学朋友的交流, 都是有一定帮助的.

​闲暇之余, 我决定再重新开启一个系列, 名为"算法精讲"系列, 从自己几年来的助教经验以及对数据结构和算法的知识出发, 谈一谈在计算机领域应用比较广泛的几类算法, 也顺便解答几道算法题目, 希望可以与同在计算机领域学习或工作的读者产生一些共鸣.