选择频道搜索
geeksforgeeks 上有很多不错的基础性计算机学科知识，其风格不过多注重理论，也不是一味的像 leetcode 那种刷题，每一篇内容篇幅安排的都较短，也有一定的知识组织架构，非常适合初学者或作为工具字典书定向查阅相关内容。 该合集内容主要针对的是算法与数据结构方面相关内容，不做 100% 的翻译且基本是机翻，所有的代码只保留 Python 版本。
问题： 给定一个具有 个元素的数组 arr[]，写一个函数可以在数组 arr[] 中查找指定的元素
示例：
Output
时间复杂度是 。
线性搜索很少被实际使用，因为其他搜索算法，如二分查找算法和哈希表比线性搜索更快。
给定一个由 个元素组成的已排序的数组 arr[]，编写一个函数来搜索 arr[] 中的给定元素 。
一个简单的方法是做线性查找，其时间复杂度是 。另一个解决该问题的方式是使用二分查找。
二分查找： 通过重复将搜索区间对半来搜索已排序的数组。从搜索整个数组的区间开始。如果搜索的值小于区间中间的项，则将区间缩小到下半部分。否则就缩小到上半部分。反复检查，直到找到值或区间为空。
我们基本可以在每一次比较后忽略掉一般的元素
递归实现二分查找：
Output :
迭代实现的二分查找
时间复杂度：
上述递推问题可用递推树法或 Master 方法求解。它属于 Master 方法的第二种情况，其递推解为 。
辅助空间： 对于迭代方式是 ，对于递归方式，需要 的堆栈空间。
与二分搜索一样，跳跃搜索也是一种排序数组的搜索算法。其基本思想是通过按固定的步骤向前跳或跳过某些元素而不是搜索所有元素来检查较少的元素（相对线性搜索）。
例如，假设我们有一个数组 arr[]，大小为 ，块（要跳转）的大小为 。然后我们搜索索引 arr[0]、arr[m]、arr[2m]……arr[km] 等等。一旦我们找到区间（arr[km] < x < arr[(k+1)m]），我们就从索引 km 执行线性搜索操作来找到元素 x。
考虑如下数组 (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). 数组长度是 16，将利用跳跃搜索 55，假设跳跃的块大小为 4，则查找顺序如下：
最佳的跳跃块大小是多少？
在最坏的情况下，我们必须进行 次跳转，如果最后检查的值大于要搜索的元素，我们将执行 比较以进行线性搜索。因此，最坏情况下的比较总数为（）。当 时取得最小值，因此，最佳步长为 .
Output:
时间复杂度：，辅助空间：
重要点：
References: https://en.wikipedia.org/wiki/Jump_search
给定一个由 个均匀分布的值组成的排序数组 arr[]，编写一个函数来搜索数组中的特定元素 。
线性搜索的复杂度是 ，跳跃搜索的复杂度是 ，二分搜索的复杂度是 。
对于排序数组中的值是均匀分布的，则插值搜索是对分搜索的改进。二分搜索总是转到中间元素进行检查。而插值搜索可以根据正在搜索的 key 的值去到不同的位置。例如，如果 key 的值更接近最后一个元素，则插值搜索可能会朝着结束侧开始搜索。
为了找到要搜索的位置，它使用以下公式：
pos的公式可以推导如下：
算法
下面是该算法的实现：
此搜索算法的名称可能会产生误导，因为它在 时间内完成搜索。名称来自它搜索元素的方式。
指数搜索有两个步骤：
怎么查找元素可能的所在范围？
这个想法是从子数组大小为 1 开始，将其最后一个元素与 进行比较，然后尝试大小 2，然后 4，依此类推，直到子数组的最后一个元素不大于 。
一旦我们找到一个索引 ，我们就知道元素必须存在于 和 之间（为什么 ？因为我们在上一次迭代中找不到更大的值），下面给出了上述步骤的实现：
时间复杂度
辅助空间： 上述二分搜索的实现是递归的，需要 空间。使用迭代二进制搜索，我们只需要 空间。
指数搜索的应用：
Reference: https://en.wikipedia.org/wiki/Exponential_search
下面是一个简单的递归实现的三元搜索函数：
在最坏的情况下，二分和三分方法中哪一种比较少？
三元搜索在进行 递归调用时，比较的次数似乎较少，但是二元搜索进行 递归调用。让我们仔细看看。
以下是在二分搜索的最坏情况下计算比较的递归公式。
以下是三元搜索最坏情况下计数比较的递归公式。
在二分搜索中，最坏情况下有 比较。在三元搜索中，最坏情况下有 次比较。
因此，三元和二元搜索的比较归结为表达式 和 的比较。 的值可以写成。由于 的值大于 1，在最坏的情况下，三元搜索比二元搜索做更多次的比较。
练习：
为什么归并排序将输入数组分成两半，为什么不分成三部分或更多部分？
选择排序算法通过从未排序的部分重复寻找最小元素（考虑升序）并将其放在开始处来对数组进行排序。该算法在给定的数组中保持两个子数组。
在选择排序的每次迭代中，从未排序的子数组中选取最小元素（考虑升序），并将其移动到已排序的子数组中。
以下示例说明了上述步骤：
时间复杂度： ，因为有两个嵌套循环。
辅助空间： 选择排序的好处在于，它不会进行超过 次的交换，而且在内存写入是一项代价高昂的操作时非常有用。
冒泡排序是最简单的排序算法，如果相邻元素顺序错误，它会重复交换相邻元素。
第一轮：
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 )，在这里，算法比较前两个元素，因为 5 > 1，交换 ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 )，因为 5 > 4，交换 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 )，因为 5 > 2，交换 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )，因为 5 < 8，不做交换
第二轮：
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 )，因为 4 > 2，交换 ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
现在，数组已经排序，但是我们的算法不知道它是否完成。该算法需要一个完整的没有任何交换的过程，它才能确定排序结束。
第三轮：
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
下面是冒泡排序的实现：
优化实现：
即使对已排序的数组进行排序，上述函数也始终运行 次。如果内环没有任何交换，可以停止。
最差和平均时间复杂度： ，当数据逆序排序时是最坏情况
最好情况下时间复杂度： ，即数组已经是排序好的情况下
辅助空间：
属于就地排序、稳定排序
由于其简单性，冒泡排序经常被用来引入排序算法的概念。在计算机图形学中，它很受欢迎，因为它能够在几乎已排序的数组中检测到非常小的错误（如两个元素的交换），并以线性复杂度（）修复它。例如，它用于多边形填充算法，其中边界线在特定扫描线（平行于 轴的线）处按其 坐标排序，随着 的增加，它们的顺序变化（两个元素交换）仅在两条线的交点处（来源：Wikipedia）
插入排序是一种简单的排序算法，其工作原理类似于对手中的扑克牌进行排序。数组实际上分为排序部分和未排序部分。未排序数组中的值将被拾取并放置在已排序数组中的正确位置。
要按升序对大小为 的数组排序：
稳定排序、就地排序、在线排序
使用场景： 当元素数较少时使用插入排序。当输入数组几乎被排序时，它也很有用。
什么是二分插入排序？
我们可以使用二分搜索来减少正常插入排序中的比较次数。二分插入排序使用二分搜索来查找在每次迭代中插入选定项的正确位置。在正常插入中，排序在最坏情况下取 （在第 次迭代中）。我们可以使用二分搜索将其缩减为 。由于每次插入都需要一系列的交换，因此该算法总体上仍具有 的最坏运行时间。具体实现参阅这里。
如何实现链表的插入排序？
具体实现参照这里。
与快速排序一样，归并排序也是一种分而治之的算法。它将输入数组分成两半分别排序，然后合并已排序的两半。merge() 函数用于合并。 是一个关键过程，它假定 和 被排序，并将两个排序的子数组合并为一个。
下图显示了示例数组 {38，27，43，3，9，82，10} 的完整合并排序过程，示例来自于 wikipedia。如果我们仔细看这个图，我们可以看到数组被递归地分成两半，直到大小变为 1。一旦大小变为 1，合并过程就开始了，直到整个数组被合并。
时间复杂度： 归并排序是一种递归算法，时间复杂度可以表示为以下递推关系：
上述递推可采用递推树法或 Master 方法求解。它属于 Master 方法的第二种情况，其递推解是 。归并排序的时间复杂度在所有 3 种情况下（最差、平均和最佳）均为 ，归并排序总是将数组分为两半，并且需要线性时间来合并两半。
典型的实现并非就地排序，属于稳定排序
归并排序的应用：
归并排序的缺点：
堆排序是一种基于二叉堆数据结构的比较排序技术。它类似于选择排序，我们首先找到最小元素并将最小元素放在开头。我们对其余的元素重复同样的过程。
什么是二叉堆？
让我们先定义一个完整的二叉树，在这个二叉树中，除了可能的最后一层外，每一层都被完全填满，所有的节点都尽可能的左移（来源维基百科）
二叉堆是一个完整的二叉树，其中项目按特殊顺序存储，使得父节点中的值大于（或小于）其两个子节点中的值。前者称为最大堆，后者称为最小堆。堆可以用二叉树或数组表示。
为什么要对二叉堆使用基于数组的表示？
由于二叉堆是一个完整的二叉树，因此它可以很容易地表示为一个数组，并且基于数组的表示是空间有效的。如果父节点存储在索引 处，则左子节点可以按计算，右子节点可以按 计算（假设索引从 0 开始）。
按递增顺序排序的堆排序算法：
如何构建堆？
Heapify 过程仅当其子节点被 Heapify 时才能应用于节点。因此，堆化必须按自下而上的顺序进行。
通过一个例子让我们了解：
就地排序，典型实现是非稳定的，稳定版可以参照这里
时间复杂度： heapify 的时间复杂度为 。createAndBuildHeap() 的时间复杂度为 ，堆排序的总体时间复杂度为 。
HeapSor t的应用
堆排序算法的用途有限，因为快速排序和归并排序在实践中效果更好。然而，堆数据结构本身被大量使用。
与归并排序一样，快速排序也是一种分而治之的算法。它选取一个元素作为轴，并围绕所选取的轴对给定数组进行分区。有许多不同版本的快速排序以不同的方式选择轴。
始终选择第一个元素作为轴。
始终选择最后一个元素作为枢轴（在下面实现）
选择一个随机元素作为轴心。
选择中间带作为轴。
快速排序的关键过程是 partition()。分区的目标是，给定一个数组和数组的一个元素 作为轴心，将 放在排序数组中正确的位置，将所有较小的元素（小于）放在 之前，将所有较大的元素（大于 ）放在 之后。所有这些都应该在线性时间内完成。
快速排序的递归版本伪代码
Partition 算法
划分的方法有很多种，下面的伪代码采用 CLRS 手册中给出的方法。逻辑很简单，我们从最左边的元素开始，跟踪较小（或等于）元素的索引作为 。在遍历时，如果我们找到一个较小的元素，我们就用 arr[i] 交换当前元素。否则我们忽略当前元素。
Pseudo code for partition()
partition() 图解 :
时间复杂度分析： 最好情况下，，最好和平均情况下都是 ，具体分析过程略。
尽管快速排序的最坏情况时间复杂度是 ，这比许多其他排序算法（如归并排序和堆排序）都要高，但是快速排序在实践中速度更快，因为它的内部循环可以在大多数体系结构和大多数实际数据中有效地实现。快速排序可以通过改变 pivot 的选择以不同的方式实现，这样对于给定的数据类型，最坏的情况很少发生。然而，当数据很大且存储在外部存储器中时，归并排序通常被认为更好。
默认实现不稳定。然而，任何排序算法都可以通过将索引作为比较参数来实现稳定。根据就地算法的广泛定义，它是就地排序算法，因为它只使用额外的空间来存储递归函数调用，而不用于操作输入。
什么是三向快速排序？
在简单的快速排序算法中，我们选择一个元素作为 pivot，围绕 pivot 对数组进行划分，并在 pivot 的左右两侧对子数组进行递归。
考虑一个有许多冗余元素的数组。例如，{1，4，2，4，2，4，1，2，4，1，2，2，2，2，4，1，4，4，4}。如果在简单快速排序中选择 4 作为轴心，我们只修复一个 4 并递归处理剩余的事件。在三向快速排序中，数组 arr[l…r] 被分为三部分：
关于快速排序在链表上的实现以及迭代方式实现可以参考：
QuickSort on Singly Linked List
QuickSort on Doubly Linked List
Iterative Quick Sort.
为什么快速排序比归并排序更适合排序数组
快速排序的一般形式是就地排序（即它不需要任何额外的存储），而归并排序需要 额外的存储， 表示数组大小，这可能非常昂贵。分配和取消分配用于归并排序的额外空间会增加算法的运行时间。比较平均复杂度，我们发现这两种类型的排序都有 平均复杂度，但常数不同。对于数组，由于使用了额外的 存储空间，归并排序较差。
快速排序的大多数实际实现都使用随机版本。随机版本的时间复杂度预期为 。最坏的情况在随机化版本中也是可能的，但最坏的情况不会出现在特定的模式（如排序数组）中，随机化快速排序在实践中效果很好。
快速排序也是一种缓存友好的排序算法，因为它在用于数组时具有良好的引用局部性。
快速排序也是尾部递归的，因此尾部调用优化已经完成。
为什么对于链表来说 MergeSort 比 QuickSort 更受欢迎？
在链表的情况下，情况不同主要是由于数组和链表的内存分配不同。与数组不同，链表节点在内存中可能不相邻。与数组不同的是，在链表中，我们可以用 额外的空间和 时间内完成插入。因此，归并排序的合并操作可以在不为链表增加额外空间的情况下实现。
在数组中，我们可以进行随机存取，因为元素在内存中是连续的。假设我们有一个整数（4 字节）数组 A，让 A[0] 的地址为 ，那么要访问 A[i]，我们可以直接访问（）处的内存。与数组不同，我们不能在链表中进行随机访问。快速排序需要大量此类访问。在链表中，为了访问第 个索引，我们必须将每个节点从头部移动到第 个节点，因为我们没有连续的内存块。因此，快速排序的开销会增加。归并排序按顺序存取数据，对随机存取的要求较低。
如何优化快速排序，以便在最坏的情况下占用 额外的空间？
