数据结构
2019-07-22 本文已影响3人
_ClariS_
排序的原则：要么浪费空间，要么浪费时间，不可能既节省空间又节省时间（二选一）
- 哈希（Hash）
只能排[0，∞)的正整数，不能排负数和小数，排序中间过程需要一个哈希表（桶），不是比较排序；
计数排序（桶排序）优于比较排序；
数组长度 length 的值为 index 里的最大值+1，例如index=66，则长度length=67;
计数排序中的桶（复杂度 O(n+max)，比快排还快。
- 计数排序——浪费桶（空间）
- 桶排序——节约空间（桶自由规定），浪费时间（桶内部还需要进行排序）
- 基数排序——桶（这里的桶也是队列）个数固定（0~9），适合排比较大的数
- 队列（Queue）
- 先进先出
- 可以用数组实现
- push（入队）—— shift（出队）
- 栈（Stack）
- 先进后出
- 可以用数组实现
- push（入栈）——shift（出栈）
- 链表（Linked List）
- 数组无法直接删除中间的一项，链表可以；若数组要删除中间项，后面的项要挨个往前移动，变动很大；数组查询很快，链表删除很快。
- 用哈希（JS里面用对象表示哈希）实现链表
-
head（链表头）、node（结点） 概念
- 树（tree）
- 由链表构成
- 举例：层级结构、DOM
- 概念：层数、深度、节点个数
二叉树的第 i 层最多有 2^(i-1)个节点数
深度为 k 的二叉树最多总共有 2^(k+1)-1个节点数 - 二叉树
- 满二叉树
- 完全二叉树
在一颗二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干接点，则此二叉树为完全二叉树
- 完全二叉树和满二叉树可以用数组实现
- 其他树可以用哈希（对象）实现
- 操作：增删改查
- 堆排序用到了 tree
- 其他：B树、红黑树、AVL树
堆排序可视
- 堆排序
堆排序可视化（最大堆）
堆排序JS代码讲解
