痛定思痛，终于决定花半年时间深入学习技术面试题，为明年的跳槽作准备。以后会把比较重要且深刻掌握的知识点记录下来，加深理解及方便学习。
今天整理的算法是堆排序，这是我花费了一天的时间才吸收到的精华。下面按照我的理解整理了堆排序的算法思想。希望能让大家一目了然。
第一：给出一个无序队列或者数组
第二：建堆---把无序数组变为大根堆或者小根堆（大根堆：父节点的值大于任意子节点的值；小根堆：父节点的值小于子节点的值）以下按照建大根堆思想描述
1.从最后一个有子节点的父节点开始调整，此处的索引值为i=n/2-1
2.比较此处父节点和子节点的值大小，把最大值的节点调整值父节点
3.依次i--找出歌父节点和相应子节点的最大值，并把最大值调整至顶堆
4.经过上面的处理后就形成了一个大根堆，最大值在顶堆
第三：顶堆和最后一个子节点交接，再从堆中剔除最后一个子节点
第四：依次比较剔除后的堆中的父节点和子节点的最大值，交换位置，把最大值调整至顶堆
第五：循环第三和第四的步骤，最后输出一个小根堆，即按照从小到大的顺序
由于时间问题来不及画图，明天会增加图纸说明方便读懂
网友评论