文档状态：编辑....

• 今日音乐
  

开

• 排序

struct item{
  type key;//排序关键字
  type satellite_data;//记录集相关数据
}

排序是对key进行排序,但是有时候satellite比较大,则对所有item添加一个指针集合,然后仅仅对指针集合进行排序,因为数据太大的话进行数据交换实在是太慢了!
所以我们关注的是key的排序,我们关注的是算法策略的形成而非工程细节的优化!
有所达故无所不至!

• 为什么要用排序
  [不清晰]可以利用排序问题的下界来证明其他问题的下界,我们可以证明一个排序问题的费平凡下界
[清晰]应用本身的需求
为了解决工程中将要面临的问题

排序类型

• 原址排序
  插入排序O(n^2)[比较排序]
堆排序 O(nlgn)[比较排序]
快速排序[比较排序]
• 变址排序
  归并排序O(nlgn)[比较排序]

决策树可以用来研究比较排序的局限,决策树模型证明了所有比较排序算法的最坏运行时间下界为
Ω(nlgn),从而证明堆排序和归并排序是渐进最优的比较排序算法.

于是为了打破Ω(nlgn)的界限,计数排序,基数排序,桶排序被引入了,其中设计到了变量k,d,d一般是key的位宽,到时候我们再进行详细介绍.

堆排序

• equ 归并排序(速度)+插入排序(空间)
• 注意堆(二叉堆)是一个数组,除了最底层该树是完全充满的,该二叉树堆是按照广度遍历将节点存放在数组中的即A[0]为ROOT,所以其父节点和子节点可以很简单的计算出,parent i/2向下取整,左子为2i,右子为2i+1,对于学过计算机组成原理的同学自然明白,通过左移右移占用的cpu周期短,可以大大提升效率,所以一些良好的堆排序,使用宏,或者内联函数实现寻