数据结构15-散列表

[toc] 散列思想散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”。 散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。 假如有 89 名选手参加学校运动会。为了方便记录成绩，每 ...
2020-12-23 数据结构

数据结构14-跳表

[toc] 跳表（Skip list）二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。把改造之后的数据结构叫作跳表（Skip list），这是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、 ...
2020-11-27 数据结构

数据结构13-二分查找

[toc] 二分查找（Binary Search）二分查找（Binary Search）算法，也叫折半查找算法。 二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。 假设数据大小是 ...
2020-11-27 数据结构

数据结构12-排序之优化

[toc] 如何选择合适的排序算法？ 线性排序算法的时间复杂度比较低，适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。 时间复杂度是 O(nlogn) 的排序算法不止一个，已经讲过的有归并排序、快速排序，后面讲堆的时候还会讲到堆排序。堆排序和快速排序都有比较多的应用，比如 J ...
2020-11-26 数据结构

数据结构11-排序之线性排序(桶排序、计数排序、基数排序)

[toc] 三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。 这几种排序算法 ...
2020-11-26 数据结构

数据结构10-排序之归并&快排

[toc] 归并排序和快速排序都用到了分治思想，非常巧妙。这两种排序算法适合大规模的数据排序。 归并排序（Merge Sort）如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。 归并排序使用的就是分治思想。分治 ...
2020-11-26 数据结构

数据结构09-排序之冒泡&插入&选择

[toc] 排序冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序. 展示动态排序网站：https://visualgo.net/zh 冒泡排序（Bubble Sort）冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如 ...
2020-11-26 数据结构

数据结构08-递归

[toc] 递归递归是一种应用非常广泛的算法（或者编程技巧）。之后我们要讲的很多数据结构和算法的编码实现都要用到递归，比如 DFS 深度优先搜索、前中后序二叉树遍历等等。 递归需要满足的三个条件： 一个问题的解可以分解为几个子问题的解 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 ...
2020-11-26 数据结构

数据结构07-队列

[toc] 队列队列跟栈一样，也是一种操作受限的线性表数据结构。先进者先出 队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并 ...
2020-11-25 数据结构

数据结构06-栈

[toc] 栈的概述栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。后进者先出，先进者后出 事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。 当 ...
2020-11-25 数据结构

数据结构05-链表

[toc] 链表介绍从图中我们看到，数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。 而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零 ...
2020-11-24 数据结构

数据结构04-数组

[toc] 数组概念数组（Array）是一种==线性表==数据结构。它用一组==连续的内存空间==，来存储一组具有==相同类型==的数据。 线性表（Linear List）：顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线 ...
2020-11-24 数据结构

数据结构03-复杂度分析(下)

复杂度分析(下)浅析最好、最坏、平均、均摊时间复杂度今天会继续讲四个复杂度分析方面的知识点，最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time c ...
2020-06-03 数据结构

数据结构01-大纲

以下两个表来自：https://www.bigocheatsheet.com/ ...
2020-06-03 数据结构

数据结构02-复杂度分析(上)

[toc] 复杂度分析(上)如何分析、统计算法的执行效率和资源消耗？数据结构和算法本身解决的是“快”和“省”的问题，即，如何让代码运行得更快，如何让代码更省存储空间。 事后统计法事后统计法：把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。 局限性： 测试结果非常依赖测试环境， ...
2020-06-03 数据结构
12