以前做一些分类问题的时候，没有过多的注意，直接调用现成的库，用起来也比较方便。最近开始研究起对抗生成网络（GANs），用到了交叉熵，发现自己对交叉熵的理解有些模糊，不够深入。...仅凭直觉来说，显而易见事件B的信息量比事件A的信息量要大。究其原因，是因为事件A发生的概率很大，事件B发生的概率很小。所以当越不可能的事件发生了，我们获取到的信息量就越大。...的取值范围是[0,1],绘制为图形如下： ? 可见该函数符合我们对信息量的直觉 2 熵 考虑另一个问题，对于某个事件，有n种可能性，每一种可能性都有一个概率p(xi)。...Q用来表示模型所预测的分布，比如[0.7,0.2,0.1] 直观的理解就是如果用P来描述样本，那么就非常完美。...在机器学习中，我们需要评估label和predicts之间的差距，使用KL散度刚刚好，即 ? ，由于KL散度中的前一部分 ? 不变，故在优化过程中，只需要关注交叉熵就可以了。
分治法思想是，将原问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后在合并这些子问题的解，最终建立原问题的解。...分治模式在每层递归时都有三个步骤： 1、分解：将原问题分解为若干子问题，这些子问题是原问题的规模较小的实例； 2、解决：递归的求解各子问题； 3、合并：合并子问题的解，得到原问题的解。...看到这里，“直觉”上可能会产生一个极大的疑问：最底层的子问题是在哪里解决的？...归并排序伪码 归并排序按照分治法的三个步骤如下： 分解：分解待排序的n个元素的序列，变成各具n/2个元素的两个子序列； 解决：递归的调用自身排序两个子序列； 合并：合并两个已排序的子序列以产生最终排序的序列...上一篇合并算法中已经解决了合并算法MERGE，归并排序就剩下如何进行分解，和递归调用了。
分治法思想是，将原问题分解为几个规模较小但类似于原问题的子问题，递归的求解这些子问题，然后在合并这些子问题的解，最终建立原问题的解。...分治模式在每层递归时都有三个步骤： 分解：将原问题分解为若干子问题，这些子问题是原问题的规模较小的实例； 解决：递归的求解各子问题； 合并：合并子问题的解，得到原问题的解。...看到这里，“直觉”上可能会产生一个极大的疑问：最底层的子问题是在哪里解决的？...归并排序伪码 归并排序按照分治法的三个步骤如下： 分解：分解待排序的n个元素的序列，变成各具n/2个元素的两个子序列； 解决：递归的调用自身排序两个子序列； 合并：合并两个已排序的子序列以产生最终排序的序列...上一篇合并算法中已经解决了合并算法MERGE，归并排序就剩下如何进行分解，和递归调用了。
归并排序 归并排序的每次分解都是一分为二，整个递归过程画成递归树之后如图所示。m(n) 的时间复杂度为 m(n/2) 的时间复杂度乘以 2，加上合并所需要的时间复杂度。...而 m(n/2) 的时间复杂度等于 m(n/4) 的时间复杂度乘以 2，加上合并所需要的时间度。以此类推，最终时间复杂度为 m(1) 乘以 n，再加上这过程的合并操作所需的时间复杂度。...机器执行递归代码的过程对应的是深度优先的方式，而我们思考递归的过程应该采用广度优先的方式，个人理解也就是在第一层的时候，我先将其子问题都当做得到了正确的解，然后基于这个我解决第一层的问题。...递归这种编程方式的背后，其实是树和堆栈这两种看似关联不大的数据结构。递归树相当于递归过程的完整示意图，也就是说当递归完成之后，将它的过程画出来之后是递归树那样子的形状。...因此可以说，递归的背后是一颗树，递归的执行过程其实是在这棵树上做深度遍历的过程，每次进入下一层就是压栈，每次退出当前层就是出栈。而所有入栈出栈的过程就形成了我们上面说的递归树的形态。
1.什么是递归 我们呢下面介绍一下递归的几个使用的场景，这个里面不会介绍像这个斐波那契数列那样的递归（就是数学函数，很容易理解），我们就拿数据结构里面的排序算法和二叉树的遍历作为例子熟悉一下这个过程 1.1...； 1.3归并排序 归并排序就和上面的快速排序有点不同了，因为归并排序是直接从中间分开，然后再把这个自己左右分开，直到分成一个一个的元素，最后把这个元素有序的组合起来即可； 下面的这个就是归并排序的过程展示...：就是分开之后合并的过程，这个合并的时候我们是使用的双指针的方法合并的（通过指针的移动）； 2.为什么会用到递归 我们在解决一个问题的时候，把这个问题分解为诸多的子问题，可以使用一个方法解决这个主问题，...但是解决子问题的时候同样可以使用这个方法解决； 3.如何理解递归 3.1递归展开细节图：这个是初学的时候，老师经常搞的一种方法，但是这个并不一定会简化我们对于这个递归问题的理解； 3.2二叉树的题目：我们在二叉树学习的时候...，最后合并两个有序数组，结束条件就是left>=right,结束递归的过程； void merge(int* nums, int left, int right) { //递归结束的出口 if (left
在大型公司的面试过程中，排序是必问的知识。...（两个已经有序的数组序列合并成一个更大的有序数组序列） 在开始排序前创建有一个和原数组a长度相同的空的辅助数组aux 单趟归并的过程如下： 首先将原数组中的待排序序列拷贝进辅助数组的相同位置中，即将a[...单趟排序的过程图解 为了更详细的描述单趟排序的过程，下面在上面的图A和图B的基础上给出每一步的图解： 我们要排序的序列是 2 4 5 9 1 3 6 7， 合并的前提是2 4 5 9 和 1 3 6 7...对上图可根据代码来理解。 ?...根据上文所讲的递归栈和调用顺序， 下面的轨迹图像就不难理解了： 从最左边的元素开始合并，而且左边的数组序列在第一轮合并后，相邻右边的数组按同样的轨迹进行合并， 直到合并出和左边相同长度的序列后，才和左边合并
47 小于 286 用双轴快排； 大于 286 用 timsort 归并排序，并在 timsort 中记录数据的连续的有序段的的位 置，若有序段太多，也就是说数据近乎乱序，则用双轴快排； 上面提到的快排的递归调用的过程中...算法描述 先拆分再归并，将一个大的无序数组，拆分成两个，先处理左边再处理右边（可以对比二叉树前序遍历），一直递归拆分直至只有一个元素然后两两进行归并，一直重复这个过程直至合并完所有的子数组得到有序的完整数组...归并排序 代码实现 如果上面的拆分和归并都理解了的话，写代码应该不难，静下心来写即可，看代码的理解的时候，如果对递归过程不好理解，可以在idea里面对代码进行打断点看全部的过程。...在合并的过程中，如果有相同的元素，可以按照顺序依次放入原数组中，这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。...归并排序和快速排序对比 快排不理解的，看我上一篇 极客算法训练笔记(六)，十大经典排序之希尔排序，快速排序 相同点： 都采用分治算法 都可以递归实现 平均时间复杂度都是O(nlogn) 不同点： 归并排序是先切分
，所以最终你会在代码中看到递归实现，后面会专门讲归并排序所蕴含的递归思想。...这一步事实上也是 「治」的过程，所谓治就是真正进行排序的过程，因为通过这一步元素 5 和 1 的顺序将被改变。 ? 之后的每一步都是如此，我们在下图中将每一步用红色数字标注了出来： ?...分治和递归就像一对好基友，永远不分离，为了看到归并排序的递归过程，我们先看一下归并排序的实现。 实现代码 归并排序包含两个过程，分和治，所以递归实现代码也相当简单。...心中一惊，为何这里的递归过程如此曲折，事实上没有什么可担心的，你将代码中的 mergeSort(arr,l,r) 理解为「分」和「递」，而将 merge(arr,l,m,r) 理解为 「治」和「归」，...，n，归并排序的空间复杂度为 量级。与插入排序，冒泡排序，还有选择排序相比，你也可以将归并排序理解为空间换时间的有效例证。
随机法 快排避免堆栈溢出 评论区大佬的笔记 Arrays.sort Timsort 谷歌V8 QuickSort排序 思考过程比答案重要，有答案来验证自己的思考是否准确在初学时期也很重要 经典排序算法...随机法 快排避免堆栈溢出 为了避免快速排序里，递归过深而堆栈过小，导致堆栈溢出，我们有两种解决办法：第一种是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归。...第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。...5 每次压入栈，都要检查栈内已存在的分区是否满足合并条件，满足则进行合并 6 最终栈内的分区被全部合并，得到一个排序好的数组 Timsort Timsort的合并算法非常巧妙： 1...学习知识每个人的理解会不同，有的人可能这么理解有的人可能那样理解。如果没有一个标杆，有些同学就会按照自己错误的理解继续学习下去。 有了标准答案，同学就可以对照答案来反思自己的理解是否正确。
因为还处在「看山是山，看水是水」的阶段。 就说归并排序吧，如果给你看代码，让你脑补一下归并排序的过程，你脑子里会出现什么场景？ 这是一个数组排序算法，所以你脑补一个数组的 GIF，在那一个个交换元素？...后序遍历二叉树大家应该已经烂熟于心了，就是下图这个遍历顺序： 结合上述基本分析，我们把nums[lo..hi]理解成二叉树的节点，srot函数理解成二叉树的遍历函数，整个归并排序的执行过程就是以下 GIF...sort函数对nums[lo..mid]和nums[mid+1..hi]递归排序完成之后，我们没有办法原地把它俩合并，所以需要 copy 到temp数组里面，然后通过类似于前文 单链表的六大技巧 中合并有序链表的双指针技巧将...换句话说，在对nuns[lo..hi]合并的过程中，每当执行nums[p] = temp[i]时，就可以确定temp[i]这个元素后面比它小的元素个数为j - mid - 1。...这道算法题其实就是归并排序算法逻辑中夹杂一点私货，但仍然属于比较难的，你可能需要亲自做一遍才能理解。 那我最后留一个思考题吧，下一篇文章我会讲快速排序，你是否能够尝试着从二叉树的角度去理解快速排序？
其核心思想是逐步将每个待排序的元素插入到已排序序列的适当位置，直到所有元素都排序完毕，这个过程类似于我们日常整理扑克牌或书籍时的插入动作 优点 （1）实现简单直观，代码易于编写和理解 （2）对小规模数据或几乎已经有序的数据效率高...稳定性分析 （1）稳定性：非递归归并排序与递归归并排序在稳定性方面保持一致，都是稳定的排序算法 （2）在归并排序的过程中，当两个相等元素分别位于不同的子数组时，合并这两个子数组时会按照它们在原数组中的顺序进行合并...在这个过程中，相同元素的相对位置不会发生变化。 时间复杂度： 最优情况：O(n log n) 非递归归并排序的时间复杂度主要取决于合并操作的次数。...O(n log n)，不受输入数组顺序的影响 空间复杂度： （1）非递归归并排序的空间复杂度主要取决于合并过程中所需的辅助空间。...在合并两个有序子数组时，需要额外的存储空间来存放合并后的数组 （2）虽然非递归实现避免了递归调用栈的开销，但仍然需要额外的空间来保存合并过程中的中间结果。
本文将详细介绍归并排序的工作原理和Python实现。 归并排序的工作原理 归并排序的基本思想是将数组不断分成两半，然后递归地对两半进行排序，最后将排序好的两半合并在一起。...分治的关键在于如何合并两个有序子数组。归并排序的工作过程如下： 将数组分成两半，直到每个子数组只包含一个元素。 递归地将子数组排序。 合并两个有序子数组，得到一个更大的有序数组。...递归地对左右两部分进行排序。 合并有序子数组的函数 merge。...它是一种高效的排序算法，不仅适用于大型数据集，还具有稳定性。 总之，归并排序是一种高效的分治排序算法，通过将数组分成两半，递归地排序子数组，然后合并有序子数组，实现了对数组的归并排序。...了解归并排序有助于理解分治算法的思想，并为排序大型数据集提供了一个强大的工具。
步骤： 将待排序的数列分成若干个长度为1的子数列 然后将这些数列两两合并；得到若干个长度为2的有序数列 再将这些数列两两合并；得到若干个长度为4的有序数列 再将它们两两合并；直接合并成一个数列为止...下面介绍的这个算法，可以适应小于 0 的数的计数排序，不过我加了很多注释，也很好理解： public void countSort(int[] arr) { // 找到最大值和最小值 int...与计数排序不同，桶排序的步骤 2 完成之后，所有元素都处于桶中，并且对桶中元素排序后，移动元素过程中不再依赖原始集合，所以可以将桶中元素移动回原始集合即可。...值取反 重复以上操作直到队列为空 视频 同样的这个体型太特殊，所以没有相关视频解析，不过好在算法过程也很好理解 public List> zigzagLevelOrder...我一直觉得，一片过长的文章，就像一堂超长的 会议/课堂，体验很不好，所以我打算再开一篇文章 在后续文章中，我将继续针对链表 栈 队列 堆 动态规划 矩阵 位运算 等近百种，面试高频算法题，及其图文解析
这是无量测试之道的第161篇原创 今天讲的内容是归并排序，为了比较容易的理解归并排序，我们首先看一道leetcode的算法题，通过该题的解题思路，会让我们更加容易的理解归并排序的思想。...开篇问题 这个题的解题思路其实就是归并排序的merge的过程。首先让我们先解这道题，便于后面更好的理解归并排序的思想。...代码理解 因为归并排序中主要用到的就是分治的思想，包含递归的编程技巧，所以我打算先贴代码再来讲解其实现思路. ...然后通过绘图的形式讲解了归并排序的divide和sort，并且通过代码实现了归并排序算法。最后，也讲解了下divide的递归实现流程。...最后的最后，希望读者朋友们通过阅读这篇文章，可以比较通俗易懂的理解归并排序算法。
写 这篇博文主要记录一些自己对于快速排序的了解，以及对快速排序的性能的分析。我将在这里记录下我对快速排序的认识和学习过程 ，用尽可能简单明了的叙述来阐述我的理解。...分治法是算法中常用的策略之一，很多算法都是基于分治法的，今天要说的快速排序也一样。为了能更好的理解快速排序，先简单的介绍一下分治法。 顾名思义，分治，可理解为分而治之。...就是把原问题（递归地）分解为多个子问题(一般是和原问题本质相同的问题，只是规模上的缩小，如果现在不能理解请看后文解释)，解决这些子问题，合并其结果，获得原问题的解。...这时候我们就能更好的理解函 数"QUICKSORT"了，它有三个参数，后面的两个参数正是用来控制问题规模的。可能有人已经看出来了，这里还体现出递归的思想：在解决的过程中调用 自身。...这时，快速排序的时间递归式为： T(n)<=T(9n/10)+T(n/10)+cn 这里，我们显示的写出了f(n)中的常数c。下图显示了这个递归过程的递归树： ?
这个递归的公式是每次都将传入的待排序数据序列一分为二，直到变成不能继续分割的最小区间单元，然后将最小区间单元数据排序后合并起来，最终返回的就是排序好的数据序列了。...图示如下： 归并排序图示 由于涉及到递归，所以归并排序从理解上要比前面三个排序要困难一些，还是建议通过这个动态图帮助理解：https://visualgo.net/zh/sorting（在界面顶部选择归并排序...二、示例代码 通过上面的分析，我们知道归并=递归+合并，对应的 Go 实现代码如下： package main import ( "fmt" ) // 归并排序 func mergeSort...归并排序的时间复杂度推导过程 归并的思路是将一个复杂的问题 a 递归拆解为子问题 b 和 c，再将子问题计算结果合并，最终得到问题的答案，这里我们将归并排序总的时间复杂度设为 T(n)，则 T(n) =...2*T(n/2) + n，其中 T(n/2) 是递归拆解的第一步对应子问题的时间复杂度，n 则是排序合并函数的时间复杂度（一个循环遍历），依次类推，我们可以推导 T(n) 的计算逻辑如下： T(n)
在合并的过程中，如果 A[p...q]和 A[q+1...r]之间有值相同的元素，那我们可以像伪代码中那样，先把 A[p...q]中的元素放入 tmp 数组。...这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。 第二，归并排序的时间复杂度是多少？ 归并排序涉及递归，时间复杂度的分析稍微有点复杂。...这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。这一点你应该很容易理解。那我现在问你，归并排序的空间复杂度到底是多少呢？...，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。...理解归并排序的重点是理解递推公式和 merge() 合并函数。同理，理解快排的重点也是理解递推公式，还有 partition() 分区函数。
一、非递归版快排 1.使用栈实现非递归版快排 在学习非递归版快排前，建议大家先学习递归版的快排，否则非递归版的快排将很难理解，这里附上本人写的快排的博客解析：【初阶数据结构与算法】八大排序算法之交换排序...，所以我们才能通过栈这个数据结构来模拟递归调用的行为，只要理解到这一点，后面的内容将会好懂得多 接着我们来正式实现非递归版的快排，首先我们需要一个栈作为辅助，可以将之前写过的栈导入到当前文件夹进行添加...，接下来我们开始学习使用队列实现非递归版快排 2.使用队列实现非递归版快排 刚刚的非递归快排就是利用栈模拟递归，因为递归的本质就是在栈区里面开辟新的函数栈帧，这个过程和我们入栈操作类似，所以我们才能使用栈实现非递归快排...这就要求我们透过归并排序看清它的本质了，它的本质就是对数组进行分组，然后两两一组进行排序，最后进行合并，如图： 所以我们就可以写代码来模拟这个过程，首先将数组的一个元素划分为一组，然后两组两组进行合并...1，然后我们就开始两组两组进行合并，合并的逻辑和递归版的归并排序合并逻辑相似，这里不再赘述 当我们将以gap个元素为一组的情况，两组两组合并完之后，就让gap * 2来调整每组元素的个数，用新的gap
通过本文的学习，读者将能够深入理解归并排序的核心思想、掌握其实现方法，并能够在实际应用中灵活运用这一强大的排序工具。...归并排序的关键在于合并两个已排序的数组段 三、实现思路 注意： 因为归并排序在合并过程中需要一个与待排序数组大小相同的临时数组来存储合并的结果。...将temp数组中的元素复制回原数组，以完成合并过程。...这是因为归并排序在合并过程中需要一个与待排序数组大小相同的临时数组来存储合并的结果。此外，如果采用递归实现归并排序，还需要额外的栈空间来保存递归调用过程中的中间状态。...在归并排序的合并过程中，如果两个相等的元素分别来自左右两个子数组，并且左子数组中的元素在右子数组中的元素之前出现，那么在合并后的数组中这两个相等的元素也会保持原来的相对顺序。
归并排序的基本思想是将待排序数组递归地分成两个子数组，分别对这两个子数组进行排序，然后再将它们合并成一个有序数组。...合并：将两个有序的子数组合并成一个有序数组。合并的过程通过比较两个子数组的元素大小，按序依次放入目标数组。 重复上述步骤，直到所有子数组都合并成一个有序数组。...归并排序的代码实现 大家可以对照着这幅图来理解： 可以看到归并排序的思想一定可以用递归来思想，接下来，我先给大家完整的代码，之后会对代码的关键部分讲解： #include #include...非递归归并排序的核心思想：归并排序的递归版从上到下拆分数组，而非递归版则从下到上逐步合并，模拟递归中“合并”的过程。...在这个过程中，我们通过循环控制子数组的长度，每次将相邻的子数组合并成更大的有序数组。
云服务器
ICP备案
实时音视频
云直播
对象存储
