Kylen Blog

数据结构和算法之美-第十二篇-跳表

什么是跳表？跳表是一种改造之后的链表。具体的改造过程就是加索引，加多级索引。如何加索引?请看下图，存储数据为：1 3 4 6 8 9 10 14 15 18每两个数建立一级索引 我们知道访问单链表中的数据只能一个一个的访问，所以单链表的查询时间复杂度是O(n)。建立了索引之后的跳表的时间复杂度是O(logn)。比如这个例子，我们建立了二级索引，如果我们要查询有序数组中的数据9，可以直接通过......

Posted by Kylen on 2019-08-22

数据结构和算法 跳表

数据结构和算法之美-第十一篇-二分查找

二分查找二分搜索算法二分查找是我们都熟识的算法，它明确的定义是：是一种在有序数组中查找某一特定元素搜索算法 二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0 由此可见，二分查找的时间复杂度是O(logn)，这是一个很可怕的数字，因为数据规模 n 再怎么大，它的对数 logn......

Posted by Kylen on 2019-08-21

数据结构和算法 二分查找

数据结构和算法之美-第十篇-桶排序、计数排序、基数排序

桶排序、计数排序、基数排序都是线性排序，它们的时间复杂度都是O(n)，这样一看好像很厉害的样子，比我们之前提到的快排、归并都要牛，使用分治的思想结合递归的手段最终的平均时间复杂度也只能做到O(nlogn)。 其实不然，因为这三种排序只能用于特定的场景，只有在适用的场景中这些排序才能派上用场。 桶排序桶排序的工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以......

Posted by Kylen on 2019-08-09

数据结构和算法 排序 桶排序 计数排序 基数排序

数据结构和算法之美-第九篇-归并排序、快速排序

归并排序归并排序使用的是分治的思想，分治算法一般都是由递归实现的。回想一下递归的细节其实和分治很像，递归的思想一般是把一个大问题拆分成几个子问题，除了数据规模不同，子问题的求解思路和大问题没有任何区别。这种把大问题拆分成小问题的的思想其实就是一种分治的思想。而分治和递归的区别也在于此，分治是一种解决问题的思想，而递归是一种编程技巧。 归并排序算法步骤： 申请空间，使其大小为两个已经排序序列......

Posted by Kylen on 2019-08-07

数据结构和算法 排序 归并排序 快速排序

数据结构和算法之美-第八篇-冒泡排序、插入排序、选择排序

排序算法的分类我最开始接触和使用最多的排序算法就是冒泡排序了（可能很多人和我一样）但是把它好好的和其他各类排序算法进行比较。很多时候我们有更好的选择。 排序算法基本分为三类： 排序算法 时间复杂度 是否基于比较 冒泡 插入 选择 O(n2) 是 快排 归并 O(nlogn) 是 桶 计数 基数 O(n) 不是 排序算法的优异几个基本概念： 原地排序：空间复杂度为O(1......

Posted by Kylen on 2019-08-06

数据结构和算法 排序 冒泡排序 插入排序 选择排序

数据结构和算法之美-第七篇-递归

前言说起算法，提的最多的就是递归、排序和二分查找，因为这些是最基础也是最经常使用的。实际工作中，递归也是一种很有效的算法或者说编程技巧。 不过有些时候总觉得递归没那么好写，得琢磨半天。。。 如何理解递归或者说什么样的问题可以用递归来解决。 一个问题的解可以被拆成几个子问题的解 这个问题与分解而出的子问题，除了数据规模不同，求解思路完全一致 存在递归终止条件，一般就是数据规模到达可以预知的最......

Posted by Kylen on 2019-08-06

数据结构和算法 递归

数据结构和算法之美-第六篇-队列

队列先进先出，类比现实生活中的排队，先到先得。 队列也是一种操作受限的线性表，支持操作：入队、出队 如下图所示 队列可以使用数组实现也可以使用链表实现基于链表实现的队列叫链式队列 12345678910111213141516171819202122232425262728293031323334class Node { constructor(v) { this......

Posted by Kylen on 2019-08-06

数据结构和算法 队列

数据结构和算法之美-第五篇-栈

栈栈是一种后进先出的数据结构，是一种“操作受限”的线性表。只允许在一端插入和删除数据。 我第一次接触这种数据结构的时候，就对它存在的意义产生了很大的疑惑。因为我觉得，相比数组和链表，栈带给我的只有限制，并没有任何优势。那我直接使用数组或者链表不就好了吗？为什么还要用这个“操作受限”的“栈”呢？事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，......

Posted by Kylen on 2019-08-05

数据结构和算法 栈

数据结构和算法之美-第四篇-链表

链表链表也是一种最基础的数据结构 链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度 也就是说链表使用零散的内存块，链表中的每个节点中存储下一个节点的指针。它就像是一种和数组“相反”的数据结构。从内存结构上看，数组使......

Posted by Kylen on 2019-08-05

数据结构和算法 链表

数据结构和算法之美-第三篇-数组

前言在大部分编程语言中，数组都是从 0 开始编号的，但你是否下意识地想过， 从 1 开始不是更符合人类的思维习惯吗？ 数组 数组（Array）是一种线性表结构，它用一组连续的内存空间，来存储一组具有相同数据类型的数据 附上维基百科中数组的定义这么看来，JavaScript中的数组其实更像Java中的容器，JavaScript中的数组可以存储不同类型的数据，长度也可变。后面提到的数组都只是这......

Posted by Kylen on 2019-07-30

数据结构和算法 数组
FEATURED TAGS
JS进阶系列 blog 数据结构和算法 排序
ABOUT ME

不知道做什么？那就尽情热爱生活吧！

RECENT POSTS
FRIENDS
ARCHIVES