数据结构

排序的原则：要么浪费空间，要么浪费时间，不可能既节省空间又节省时间（二选一）

1. 哈希（Hash）
   只能排[0，∞)的正整数，不能排负数和小数，排序中间过程需要一个哈希表（桶），不是比较排序；
   计数排序（桶排序）优于比较排序；
   数组长度 length 的值为 index 里的最大值+1，例如index=66，则长度length=67;
   计数排序中的桶（复杂度 O(n+max)，比快排还快。

• 计数排序——浪费桶（空间）
• 桶排序——节约空间（桶自由规定），浪费时间（桶内部还需要进行排序）
• 基数排序——桶（这里的桶也是队列）个数固定（0~9），适合排比较大的数

2. 队列（Queue）

• 先进先出
• 可以用数组实现
• push（入队）—— shift（出队）

3. 栈（Stack）

• 先进后出
• 可以用数组实现
• push（入栈）——shift（出栈）

4. 链表（Linked List）

• 数组无法直接删除中间的一项，链表可以；若数组要删除中间项，后面的项要挨个往前移动，变动很大；数组查询很快，链表删除很快。
• 用哈希（JS里面用对象表示哈希）实现链表

• head（链表头）、node（结点） 概念

  
  

5. 树（tree）

• 由链表构成
• 举例：层级结构、DOM
• 概念：层数、深度、节点个数
  二叉树的第 i 层最多有 2^(i-1)个节点数
  深度为 k 的二叉树最多总共有 2^(k+1)-1个节点数
• 二叉树
• 满二叉树
• 完全二叉树

  在一颗二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干接点，则此二叉树为完全二叉树

• 完全二叉树和满二叉树可以用数组实现
• 其他树可以用哈希（对象）实现
• 操作：增删改查
• 堆排序用到了 tree
• 其他：B树、红黑树、AVL树
  堆排序可视

5. 堆排序
   堆排序可视化（最大堆）
   堆排序JS代码讲解