astipsy

上两节讲到，因为二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？ 实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表（Skip …

上一节讲述了二分查找的原理，并且介绍了最简单的一种二分查找的代码实现。接下来讲几种二分查找的变形问题。 不知道你有没有听过这样一个说法：“十个二分九个错”。二分查找虽然原理极其简单，但是想要写出没有 Bug 的二分查找并不容易。 唐纳德·克 …

无处不在的二分思想 二分查找是一种非常简单易懂的快速查找算法，生活中到处可见。比如说，我们现在来做一个猜字游戏。我随机写一个 0 到 99 之间的数字，然后你来猜我写的是什么。猜的过程中，你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为 …

如何选择合适的排序算法？ 如果要实现一个通用的、高效率的排序函数，应该选择哪种排序算法？ 前面讲过，线性排序算法的时间复杂度比较低，适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。 如果对小规模数据进行排序，可以选择 …

这一节讲述三种时间复杂度是O(n)的排序算法：桶排序、技术排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以又叫作线性排序（Linear sort）。之所以能做到线性的时间复杂度，主要原因是，这三个算法是非基于比较的排序算法，都不涉 …

上一节讲述了冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是O(n²)，比较高，适合小规模数据的排序。这一节讲两种时间复杂度为O(nlogn)的排序算法，归并排序和**快速排序***。 归并排序原理 归并排序的核心思想很简单 …

如何分析一个“排序算法” 学习排序算法，我们除了学习它的算法原理、代码实现之外，更重要的是要学会如何评价、分析一个排序算法。那分析一个排序算法，要从哪几个方面入手呢？ ==排序算法的执行效率== 对于排序算法执行效率的分析，我们一般会从这几 …

理解“递归” 递归是一种应用非常广泛的算法（或者编程技巧）。之后我们要讲的很多数据结构和算法的编码实现都要用到递归，比如DFS深度优先搜索、前中后序二叉树遍历等等。 不过，别看说了这么多，递归本身可是一点儿都不“高冷”，咱们生活中就有很多用 …

理解“队列” 队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的只能站末尾。先进者先出，这就是典型的“队列”。 我们知道，栈只支持两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本 …

理解“栈” 关于“栈”，有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个的放；取的时候，我们也是从上往下一个一个的依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。 从栈的操 …