常见数据结构

数据结构

1. 哈希表（Hash Table）
   • 计数排序中的桶（复杂度 O(n+max)，比快排还快
   • 桶排序 与计数排序的区别
   • 基数排序 与计数排序的区别
2. 队列（Queue）
   • 先进先出
   • 可以用数组实现
   • 举例：排队
3. 栈（Stack）
   • 先进后出
   • 可以用数组实现
   • 举例：盗梦空间
4. 链表（Linked List）
   • 数组无法直接删除中间的一项，链表可以
   • 用哈希（JS里面用对象表示哈希）实现链表
   • head、node 概念
5. 树（tree）
   • 举例：层级结构、DOM
   • 概念：层数、深度、节点个数
   • 二叉树
   • 满二叉树
   • 完全二叉树
   • 完全二叉树和满二叉树可以用数组实现
   • 其他树可以用哈希（对象）实现
   • 操作：增删改查
   • 堆排序用到了 tree
   • 其他：B树、红黑树、AVL树

堆排序可视化：https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
堆排序JS代码完整讲解（看到最后）：http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/

哈希&计数排序

1. 所有满足一个键一个值这样结构的就叫做哈希；

2. 哈希的用法？计数排序要用到哈希；

3. 随机快排的复杂度：对于一个数组，如果我们使用插扑克牌的方式进行排序，就需要将一个数跟排好的数字们进行比较，只要要做循环比较，复杂度就是NlogN，即N乘以N关于2的对数

4. 计数排序可以做到更快，数组其实也是哈希，因为其符合一个数字对应一个值这样的关系，数组其实就是对象；

5. 计数排序

   • 第一步：入桶，将数组放入哈希中，定义一个数组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
     
     

     牌放进去后，排序其实就已经好了

6. 计数排序的复杂度是n+max，入桶的时候遍历一遍，为n，出桶的时候遍历哈希的length，就是max

7. 计数排序比快排要快，但是有两个缺点

   • 需要额外的桶
   • 无法对小数（会导致桶无数个）和负数排序

桶排序和基数排序（Radix Sort）

1. 桶排序是一个桶里面放多个数字，如第一个桶放0-9，第二个桶放10-19，第三个桶放20-29等等
2. 快排之所以快的原因是因为快排每次都会把数字分为左边和右边，这样左边的数字永远都不用跟右边的数字作对比，桶排序也是这样，每一个数字都会放到一个桶里面，第一个桶里面的数字永远不需要跟第二个桶作对比，只需要在内部进行排序，其中多少个桶自己定，桶内数字进行排序；计数排序比较浪费桶，桶排序节约桶，但是要做二次排序。
3. 排序的一个原则是，要么浪费空间，要么浪费时间。不可能兼得。
4. 应用情景：高考总分进行排序，可以分成七个桶
5. 基数排序（1-十万的数字，最好用基数排序）：
   • 基数排序的依据是以10为基准，即按照个位值，十位值，百位值，千位值以此类推放到0-9的10桶里面进行排序

   • 我们首先由一堆数字

     
     
     image.png

   • 先按照个位数进行排序，然后按照桶依次出桶，可以保证个位数的排列顺序从小到大

     
     
     image.png
     
     
     image.png

   • 按照十位数进行排序，然后按照桶依次出桶，可以保证十位数的排列顺序从小到大

     
     
     image.png
     
     
     image.png

   • 按照百位数进行排序，然后按照桶依次出桶，可以保证百位数的排列顺序从小到大

     
     
     image.png
     
     
     image.png

   • 按照千位数进行排序，然后按照桶依次出桶，可以保证千位数的排列顺序从小到大

     
     
     image.png
     
     
     image.png

队列和栈

1. 队列，先进先出，如12306的排队系统，上面的基数排序就是用到队列，先排的桶先进行出桶操作

   
   
   image.png

2. 栈，先进后出，上面基数排列中，对于一个桶里面的数值，就是先进后出，运用栈

   
   
   image.png

链表和树

情景：我们有一个数组，想要将第三个位置删除怎么办？将第四个位置的值赋给第三个，第五个赋给第二个，到最后，最后一个空掉了，直接删除，还需要将length改成，当前序列最大值加1。会产生很大的动静

这种情况下，我们就要使用链表，链表是动态的数组，要联系到哈希

链表

1. 我们有一个对象a1，有两个哈希，一个是value，表示值，一个是next，表示指向的对象；同样，我们还有a2，a3；通过next的对应关系，这三个对象是链接起来的

   
   
   image.png

2. 但是当我们将a1的next改成a3，那么a2就不被指向了，无形中被删除了

   
   
   image.png
3. 这下我们只需要改一下引用就可以实现删除的效果了

4. 我们通过JS实现一个链表：

   
   
   image.png

5. 当我们要删除第二个的时候，可以通过以下操作

   
   
   image.png
6. JS一般很少用链表，只要使用一个哈希指向另一个哈希，就是链表
7. 链表删除某一个很好实现，但是如果想取到第n项，很复杂，即删除容易，查询难
8. 列表中有两个概念，一个是head，其他叫节点node，表头也是node

树（重要）

1. 只要是层级结构，就用到树。

2. 哈希之间满足如下的关系就是一个树

   
   
   image.png
3. 层数：从上往下分别是第一层，第二层，第三层
   深度：一共多少层，这边是3、
   节点个数：9个节点，每一个哈希就是一个节点，分为叶子节点（没有后代节点）、非叶子节点

4. 二叉树：没次顶多分两个叉，可以是一个叉

   
   
   image.png

5. 满二叉树：叶子是长满的二叉树

   
   
   image.png

6. 有关满二叉树的节点个数

   
   
   image.png

7. 完全二叉树，最后一层一定是左边连续长

   
   
   image.png

8. 数组实现满二叉树和完全二叉树，根据上面数据存储的位置，我们可以通过这些数据找到对应的值，也就是数组可以存储满二叉树和完全二叉树

   
   
   image.png

堆排序

https://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
最大堆：堆顶始终保持最大
最大堆调整
堆排序可视化：https://www.cs.usfca.edu/~galles/visualization/HeapSort.html