数据结构总结

个人对数据结构基础知识总结: hash，queue，stack，链表，树，排序算法等

目录

1. 数据结构
2. 堆排序
   1. 堆排序时间复杂度:
   2. 堆排序过程

数据结构

数据结构笔记

堆排序

排序算法中有一个叫做“归并排序”或者“合并排序”的算法，它用到的就是分而治之的思想，而它的时间复杂度就是N*logN，此算法采用的是二分法，所以可以认为对应的对数函数底数为2，也有可能是三分法，底数为3，以此类推。

堆排序时间复杂度:

初始化堆栈过程时间：O(n)

更改堆元素后重建堆时间：O(nlogn)

堆排序过程

规则（1.堆排序的二叉树必须是完全二叉树 2.从右往左依次遍历）

1. 先比较最右边相邻叶子节点谁的值大，较大值的叶子节点与其父节点比较。若父节点较大则key值不换，若父节点较小则与叶子节点交换key值。
2. 根据过程1的步骤从右往左依次遍历其余相邻叶子节点与其父节点。
3. 比较 “倒数2层级组成的小树” 最右边的相邻节点谁的值大，较大值的节点与其父节点比较。若其父节点较大则key值不换。若其父节点较小则与该节点交换key值，并且进行过程1，2。
4. 根据过程1的步骤从右往左依次遍历其余相邻节点与其父节点。
5. 比较 “倒数3层级组成的小树” 最右边的相邻节点谁的值大，较大值的节点与其父节点比较。若其父节点较大则key值不换。若其父节点较小则与该节点交换key值，并且进行过程3，4。
6. 重复以上操作推理的下一步操作，直到确定到根节点的key值。
7. 然后将根节点与最右边叶子节点交换key值，取消该叶子节点的堆排序过程。
8. 将根节点与其子节点较大者的key值进行比较，若根节点大则不交换，若根节点小则交换Key值。重复推理操作，若中途不交换则结束比较，否则依次比较每个层次父节点与子节点大小，并且交换key值直至叶子节点。
9. 重复过程7，8。直到堆排序完成。