数据结构 考研(数据结构考研真题)

数据结构 考研，数据结构考研真题

0-概述

排序算法分类

常见的排序算法可以分为以下两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(n*logn)，因此也称为非线性时间比较类排序。

非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

对于比较类排序，其时间复杂度不能突破O(n*logn)，因为所有的比较动作可以构成一棵比较树（三叉树，每个分支对应<,=,>），N个元素的全排列数目为N!，即树中节点的个数为N!，则树高为log3(N!)，而数学上可以证明：log3(N!)=Ω(n*logn)，这就是基于比较的排序算法的时间复杂度下界。

对于非比较类排序，其可以达到线性时间复杂度，不过这一般是通过牺牲空间来换取的。

数据结构 考研(数据结构考研真题)