0-概述
排序算法分类
常见的排序算法可以分为以下两大类：
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(n*logn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
对于比较类排序，其时间复杂度不能突破O(n*logn)，因为所有的比较动作可以构成一棵比较树（三叉树，每个分支对应,=,），N个元素的全排列数目为N!，即树中节点的个数为N!，则树高为log3(N!)，而数学上可以证明：log3(N!)=Ω(n*logn)，这就是基于比较的排序算法的时间复杂度下界。
对于非比较类排序，其可以达到线性时间复杂度，不过这一般是通过牺牲空间来换取的。