排序算法是计算机技术中最基本的算法,许多复杂算法都会用到排序。尽管各种排序算法都已被封装成库函数供程序员使用,但了解排序算法的思想和原理,对于编写高质量的软件,显得非常重要。本文介绍了常见的排序算法,从算法思想,复杂度和使用场景等方面做了总结。

LCA(Least Common Ancestors),即最近公共祖先,是指这样一个问题:在有根树中,找出某两个结点u和v最近的公共祖先。 RMQ即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题,本文介绍了当前解决这两种问题的比较高效的算法。