资讯专栏INFORMATION COLUMN

数据结构以及相关排序

Brenner / 2751人阅读

摘要:桶排序与计数排序的区别桶排序中一个桶可以放一个范围内的多个数据,在各个桶中又可以用其他方法排序,其快速之处在于只用对比同一个桶内的数字而无需与其他桶的数字作对比。与计数排序相比,桶排序需要作二次对比,但可省略桶的个数。

哈希表(Hash Table)

所有符合键值对即key-value的结构就是哈希。数组其实也是一种哈希。

计数排序(复杂度(n+max))无法统计负数和小数,需要一个hash表,其桶排序的极限比快排(复杂度NLogN)还快。

数组的长度(length)不是指数组的个数,而是index最大值+1。如index=66,则length=67。

桶排序与计数排序的区别:

桶排序中一个桶可以放一个范围内的多个数据,在各个桶中又可以用其他方法排序,其快速之处在于只用对比同一个桶内的数字而无需与其他桶的数字作对比。与计数排序相比,桶排序需要作二次对比,但可省略桶的个数。

基数排序与计数排序的区别:

基数排序是从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。其最大的好处是可以用最多十个桶来排序非常大的数字而无需浪费大量的桶,但是要作多次对比。

队列(Queue)

队列的特点是先进先出(push-shift),可以用数组实现
举例:排队

栈(Stack)

栈的特点是先进后出(push-pop),也可以用数组实现
举例:盗梦空间

链表(Linked List)

数组无法直接删除中间的一项,链表可以

用哈希(JS里面用对象表示哈希)实现链表,哈希里面指向了哈希

head:第一个哈希对象,即链表的表头,找到表头便可找到后面的所有项。

node:节点,表头也是节点。

链表与数组相比存在的优缺点:

链表与数组相比,其优点是可随意删除任何一项,而其缺点是很难取到链表的第n项。即数组查询很快,链表删除很快。

树(tree)

举例:层级结构、DOM

如上图所示:层数,从0开始,共两层;深度即一共有多少层,上图深度为3;节点:每一个哈希就是一个节点,上图节点个数为9:其中没有子节点的节点称为叶子节点。

二叉树(Binary tree):每个节点最多只可分两个分支。

满二叉树(Full Binary tree):一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。

完全二叉树(Complete Binary tree):一棵二叉树中,除最后一层外,若其余层都是满的,并且UI后一层或者是满的,或者是在右边缺少连续若干节点。

完全二叉树和满二叉树可以用数组实现,其他树可以用哈希(对象)实现。

堆排序用到了tree:
1.堆排序可视化
2.堆排序JS代码完整讲解

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/98345.html

相关文章

  • 推你想看的,Twitter如何在信息流中大规模应用深度学习

    摘要:在信息流排序方面,运用了的深度学习模型,并在准确度方面获得了显著的成果,促进了用户增长和参与度的提升。大型的研究团队被组建起来,很多野心勃勃的项目基于各种原因开始使用深度学习。基于上述的各种原因,我们认为深度学习是更好的方案。 不知道微博上多久没有收到主动推送的关心的亲友消息了;广告除外。可见信息流做好不是一件容易的事情。Twitter 在信息流排序方面,运用了的深度学习模型,并在准确度方面...

    tinysun1234 评论0 收藏0

发表评论

0条评论

Brenner

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<