数据结构
- 哈希表（Hash Table）
- 队列（Queue）
- 先进先出
- 可以用数组实现
- 举例：排队
- 栈（Stack）
- 先进后出
- 可以用数组实现
- 举例：盗梦空间
- 链表（Linked List）
- 数组无法直接删除中间的一项，链表可以
- 用哈希（JS里面用对象表示哈希）实现链表
- head、node 概念
- 树（tree）
堆排序可视化：https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
堆排序JS代码完整讲解（看到最后）：http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
哈希&计数排序
所有满足一个键一个值这样结构的就叫做哈希；
哈希的用法？计数排序要用到哈希；
随机快排的复杂度：对于一个数组，如果我们使用插扑克牌的方式进行排序，就需要将一个数跟排好的数字们进行比较，只要要做循环比较，复杂度就是NlogN，即N乘以N关于2的对数
计数排序可以做到更快，数组其实也是哈希，因为其符合一个数字对应一个值这样的关系，数组其实就是对象；
-
计数排序
-
第一步：入桶，将数组放入哈希中，定义一个数组a，定义一个空哈希，这个哈希有无数个桶，我们遍历a，将a中的值对应放到哈希的桶里面，比如2就放到第二个桶，56就放到第56个桶；最后哈希记录的形式就是将每个桶中含有的数字个数记录下来，如第2个桶有一个，第三个桶有两个，分别代表的就是我有一个2，两个3；
image.png -
第二步：出桶，遍历哈希，首先碰到的一个问题就是最大的哈希值是什么？我们这儿将数组a的最大值作为最大哈希值，但是最大值并不是哈希的length，最大值应该是哈希的length-1，因为还有一个叫0的桶，这些桶里面有的有数值，有的没有数值；(很多语言数组的length指的不是个数，而是里面key中最大的数字下标加1；)定义一个空数组b，从小到大地遍历这一个一个桶，如果0桶里面的数值为1，则将一个0放入b中，如果1桶中有，则按照相应个数依次将1放入b中，以此类推。所有的桶从小到大或者从大到小遍历，按照桶中的个数将对应数值依次放入b中，这样就达到了排序的效果
image.png
牌放进去后，排序其实就已经好了
-
计数排序的复杂度是n+max，入桶的时候遍历一遍，为n，出桶的时候遍历哈希的length，就是max
-
计数排序比快排要快，但是有两个缺点
- 需要额外的桶
- 无法对小数（会导致桶无数个）和负数排序
桶排序和基数排序（Radix Sort）
- 桶排序是一个桶里面放多个数字，如第一个桶放0-9，第二个桶放10-19，第三个桶放20-29等等
- 快排之所以快的原因是因为快排每次都会把数字分为左边和右边，这样左边的数字永远都不用跟右边的数字作对比，桶排序也是这样，每一个数字都会放到一个桶里面，第一个桶里面的数字永远不需要跟第二个桶作对比，只需要在内部进行排序，其中多少个桶自己定，桶内数字进行排序；计数排序比较浪费桶，桶排序节约桶，但是要做二次排序。
- 排序的一个原则是，要么浪费空间，要么浪费时间。不可能兼得。
- 应用情景：高考总分进行排序，可以分成七个桶
- 基数排序（1-十万的数字，最好用基数排序）：
- 基数排序的依据是以10为基准，即按照个位值，十位值，百位值，千位值以此类推放到0-9的10桶里面进行排序
-
我们首先由一堆数字
image.png -
先按照个位数进行排序，然后按照桶依次出桶，可以保证个位数的排列顺序从小到大
image.png
image.png -
按照十位数进行排序，然后按照桶依次出桶，可以保证十位数的排列顺序从小到大
image.png
image.png -
按照百位数进行排序，然后按照桶依次出桶，可以保证百位数的排列顺序从小到大
image.png
image.png -
按照千位数进行排序，然后按照桶依次出桶，可以保证千位数的排列顺序从小到大
image.png
image.png
队列和栈
-
队列，先进先出，如12306的排队系统，上面的基数排序就是用到队列，先排的桶先进行出桶操作
image.png -
栈，先进后出，上面基数排列中，对于一个桶里面的数值，就是先进后出，运用栈
image.png
链表和树
情景：我们有一个数组，想要将第三个位置删除怎么办？将第四个位置的值赋给第三个，第五个赋给第二个，到最后，最后一个空掉了，直接删除，还需要将length改成，当前序列最大值加1。会产生很大的动静
这种情况下，我们就要使用链表，链表是动态的数组，要联系到哈希
链表
-
我们有一个对象a1，有两个哈希，一个是value，表示值，一个是next，表示指向的对象；同样，我们还有a2，a3；通过next的对应关系，这三个对象是链接起来的
image.png -
但是当我们将a1的next改成a3，那么a2就不被指向了，无形中被删除了
image.png - 这下我们只需要改一下引用就可以实现删除的效果了
-
我们通过JS实现一个链表：
image.png -
当我们要删除第二个的时候，可以通过以下操作
image.png - JS一般很少用链表，只要使用一个哈希指向另一个哈希，就是链表
- 链表删除某一个很好实现，但是如果想取到第n项，很复杂，即删除容易，查询难
- 列表中有两个概念，一个是head，其他叫节点node，表头也是node
树（重要）
- 只要是层级结构，就用到树。
-
哈希之间满足如下的关系就是一个树
image.png - 层数：从上往下分别是第一层，第二层，第三层
深度：一共多少层，这边是3、
节点个数：9个节点，每一个哈希就是一个节点，分为叶子节点（没有后代节点）、非叶子节点 -
二叉树：没次顶多分两个叉，可以是一个叉
image.png -
满二叉树：叶子是长满的二叉树
image.png -
有关满二叉树的节点个数
image.png -
完全二叉树，最后一层一定是左边连续长
image.png -
数组实现满二叉树和完全二叉树，根据上面数据存储的位置，我们可以通过这些数据找到对应的值，也就是数组可以存储满二叉树和完全二叉树
image.png
堆排序
https://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
最大堆：堆顶始终保持最大
最大堆调整
堆排序可视化：https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
