数据结构以及相关排序

2018-10-14 admin

哈希表(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

clipboard.png

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

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

clipboard.png

  • 满二叉树(Full Binary tree):一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。
  • 完全二叉树(Complete Binary tree):一棵二叉树中,除最后一层外,若其余层都是满的,并且UI后一层或者是满的,或者是在右边缺少连续若干节点。
  • 完全二叉树和满二叉树可以用数组实现,其他树可以用哈希(对象)实现。

原文链接:https://segmentfault.com/a/1190000016675029

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-42623.html

文章标题:数据结构以及相关排序

相关文章
JavaScript实现快速排序的方法
目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934–)于1960时提出来的。 "快速排序"的思想很...
2017-03-27
对JavaScript的全文搜索实现相关度评分的功能的方法
全文搜索,与机器学习领域其他大多数问题不同,是一个 Web 程序员在日常工作中经常遇到的问题。客户可能要求你在某个地方提供一个搜索框,然后你会写一个类似 WHERE title LIKE %:query% 的 SQL 语句实现搜索功能。一开...
2017-03-24
Vue.js bootstrap前端实现分页和排序
写之前先抱怨几句。本来一心一意做.net开发的,渐渐地成了只做前端。最近项目基本都用java做后台,我们这些.net的就成了前端,不是用wpf做界面,就是用html写web页面。 深知自己前端技术不足,以前虽说用asp.net前后台都做,但...
2017-03-14
javascript实现Table排序的方法
本文实例讲述了javascript实现Table排序的方法。分享给大家供大家参考。具体实现方法如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML ...
2017-03-23
JavaScript实现表格点击排序的方法
本文实例讲述了JavaScript实现表格点击排序的方法。分享给大家供大家参考。具体分析如下: 这里实现基于JS的表格点击排序效果,可以根据表格内的数据大小自动按顺序排列,股票网站常会见到这种功能。 <html> <hea...
2017-03-23
JSON相关知识汇总
JSON:JavaScript 对象表示法(JavaScript Object Notation) JSON 语法规则 数据在名称/值对中 数据由逗号分隔 花括号保存对象 方括号保存数组 JSON有6种类型的值: 对象、数组、字符串、数字、...
2017-03-25
javascript实现Table间隔色以及选择高亮(和动态切换数据)的方法
本文实例讲述了javascript实现Table间隔色以及选择高亮(和动态切换数据)的方法。分享给大家供大家参考。具体实现方法如下: <!DOCTYPE html PUBLIC "-//W3C/...
2017-03-23
简述AngularJS相关的一些编程思想
在过去的几个月里,我一直遨游于Angular的世界。如今回想起来,很难想象在没有类似于Angular.js, Backbone.js以及其伙伴Underscore.js这些数据绑定框架下我每天如何去编写一个大型前端应用。我不敢相信我已经用它...
2017-03-24
javascript相关事件的几个概念
客户端javascript程序采用了异步事件驱动编程模型。 相关事件的几个概念: **事件类型(event type):**用来说明发生什么类型事件的字符串; **事件目标(event target):**发生事件的对象; **事件处理程序...
2017-03-23
JavaScript中用sort()方法对数组元素进行排序的操作
JavaScript数组sort()方法排序数组的元素。 语法 array.sort( compareFunction ); 下面是参数的详细信息: compareFunction : 指定一个函数,定义排序次序。如果省略,数组字典顺序...
2017-03-24
回到顶部