上节介绍了链表的基本操作史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言) https://cloud.tencent.com/developer/article/1826524 这节介绍链表的...0.稳定排序和原地排序的定义 稳定排序： 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中...像冒泡排序，插入排序，基数排序，归并排序等都是稳定排序 原地排序： 基本上不需要额外辅助的的空间，允许少量额外的辅助变量进行的排序。就是在原来的排序数组中比较和交换的排序。...像选择排序，插入排序，希尔排序，快速排序，堆排序等都会有一项比较且交换操作(swap(i,j))的逻辑在其中，因此他们都是属于原地(原址、就地)排序，而合并排序，计数排序，基数排序等不是原地排序 1.冒泡排序...*/ unsort = phead->next; /*只含有一个节点的链表的有序链表：可根据图11来理解。
常见排序算法复杂度图片n^2除nlogn在不同数据规模下的结果图片常见排序算法算法可视化来源：http://visualgo.net/冒泡排序：时间复杂度O(n^2)比较相邻元素，如果第一个比第二个大，...排序链表（medium）给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。...你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。...超过k时，出堆 h.poll(); } } return h.peek();};方法2:堆排序图片思路：利用原地堆排序的思想，将前k-1大的元素加入队尾，...== i) { swap(nums, i, largest); //找到左右节点中大的元素交换 //递归交换后面的节点 maxHeapify
今天和大家聊的问题叫做 删除排序数组中的重复项，我们先来看题面： https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array...题意 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。...不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。...题解 数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j是快指针。只要 nums[i] = nums[j] ，我们就增加 j 以跳过重复项。...LeetCode刷题实战21：合并两个有序链表 LeetCode刷题实战23：合并K个升序链表 LeetCode刷题实战24：两两交换链表中的节点 LeetCode刷题实战25：K 个一组翻转链表
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。 插入排序算法： 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。...每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 重复直到所有输入数据插入完为止。...单向链表中开头的两个结点交换。假设，left,right是表头的两个结点。...void insert(ListNode* left, ListNode*right,ListNode* data) {//在两个链表结点中插入新的结点 left->next = data...2. left,right分别为已排序链表的最左端结点，和最右端结点，初始时刻，left=head,right=head->next。如果这个两个结点逆序，利用操作1交换它们。 3.
存储在每个节点中的数据项大于或等于存储在其子节点中的数据项。 ? image Min-Heap： Min-heap是一个二叉树。它是完整的。存储在每个节点中的数据小于存储在其子节点中的数据项。 ?...优先级队列的元素根据其自然顺序排序，或者由队列构建时提供的比较器排序。 ? image 3.算法 算法是一种定义明确的过程，允许计算机解决问题。有很多算法。...简单的排序算法是冒泡排序，选择排序和插入排序。 冒泡排序：这是最简单的排序算法。我们从数组的开头开始，如果第一个元素大于第二个元素，则交换前两个元素。...线性搜索：线性搜索是一种在列表中查找目标值的方法。它按顺序检查列表中每个元素的目标值，直到找到匹配项或者直到搜索完所有元素为止。 ?...合并排序：将数组分成两半，对每一半进行排序，然后将它们合并在一起。这些半部分中的每一部分都应用了相同的排序算法。最终，它合并了两个单元素数组。O（nlogn）平均值和最差值。 ?
代码逻辑在处理头结点和尾结点的时候，是否能正常工作 经典链表操作案例： * 单链表反转 * 链表中环的检测 * 两个有序的链表合并 * 删除链表倒数第 n 个结点 * 求链表的中间结点 【03-栈&队列...当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。 栈主要包含两个操作，入栈和出栈。 实际上，栈既可以用数组来实现，也可以用链表来实现。...A:冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。 * Q:第二，冒泡排序是稳定的排序算法吗？...A:在冒泡排序中，只有交换才可以改变两个元素的前后顺序。...（因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间） 【快速排序（Quicksort）】 快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择
23.并查集 24.其他类型题 常见排序算法复杂度 d s n^2除nlogn在不同数据规模下的结果 ds_114 常见排序算法 算法可视化来源：http://visualgo.net/ 冒泡排序...超过k时，出堆 h.poll(); } } return h.peek(); }; 方法2:堆排序 ds_156 思路：利用原地堆排序的思想...== i) { swap(nums, i, largest); //找到左右节点中大的元素交换 //递归交换后面的节点 maxHeapify...排序链表（medium） ds_199 动画过大，点击查看 方法1:自顶向下 思路：用归并排序的思路，先不断分割，知道每个子区间只有一个节点位置，然后开始合并。...== null) {//两条链表还有节点没合并完，直接合并过来 temp.next = temp1; } else if (temp2 !
可能有人会有疑问：我用数组链表在头尾两端可伸可缩，为毛要用只能在头部操作的栈结构呢？ 这种FILO的结构当然是只适用于FILO的场景。...如果我们将数组/链表这种结构封装为栈，就可以只使用其pop/push的API，屏蔽掉实现细节。 应用场景： 1.编辑器的redo/undo操作。 2.浏览器的前进/后退操作。...所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。...小规模数据排序 在小规模数据下，冒泡排序/选择排序/插入排序实现较为简单，排除不稳定的选择排序，插入排序（可类比打扑克抓牌时的排序思想）比冒泡排序（最大元素依次往后冒）好在交换次数少，小规模下排序效率更高...子序列有序了，再合并起来有序的子序列，整体就排好序了。 归并排序是外部排序。每次合并操作都需要申请额外的内存空间，在合并完成之后，临时开辟的内存空间就被释放掉了。
链表的形式 1.3.1. 单向链表 所有的链表节点中都只保存了指向下一个节点地址的信息。...n+1节点指向m，这样就实现了链表的局部反转。...对于链表中的两个节点，在两两交换之后，原来的链表头结点变成了第二个节点，原来的第二个节点就变成了新的头结点，其余节点的交换就可以通过递归来实现。...删除排序链表中的重复元素（1） 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。...图片 插入排序的动画演示如上，从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
题意 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。...不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。...该解法与 删除排序数组中的重复项 的解法十分相似。...，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。...LeetCode刷题实战21：合并两个有序链表 LeetCode刷题实战23：合并K个升序链表 LeetCode刷题实战24：两两交换链表中的节点 LeetCode刷题实战25：K 个一组翻转链表
归并排序 归并排序和之前的冒泡排序、插入排序和选择排序不同，其蕴含了一种分治的思想，在本文中我们会详细说明。...归并排序也就不是一个原地排序算法了，原地排序算法的空间复杂度为 . 稳定性分析 ? 这幅图中，可以看到归并排序是稳定的排序算法，排序前后，数组中两个4的相对位置没有发生变化。...归并排序稳定的根本原因在合并的时候对值相同的两个关键字不存在交换的可能性。 归并排序相关问题摘要 关于归并排序的问题还有很多，下面给大家列举一些，之后的文章中都会一一向大家介绍。...与数组相比，归并排序在单链表上进行排序的优势何在？ 如何实现一个空间复杂度为 ，时间复杂度为 的归并排序？ 三路归并排序如何实现和操作？...如何让今天讲的归并排序变成一个原地排序算法（In-place Algorithm)？ 迭代形式的归并排序又该如何实现？
== findIndex) { this.swap(index, findIndex);//交换当前元素和左右节点中value小的 index...合并K个升序链表 (hard)给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。...，每次归并不断合并两个有序链表，直到合并完所有分治后的链表复杂度：时间复杂度O(n * logk)，n是每个链表节点数，k个链表个数，每次归并，链表数量较少一半，复杂度是O(logk)，将两个链表合并成一个顺序链表复杂度是...lists.length) { return null; } // 合并两个排序链表 const merge = (head1, head2) => { let...个排序链表，可以分成两部分，前k/2个链表和后k/2个链表 // 如果将这前k/2个链表和后k/2个链表分别合并成两个排序的链表，再将两个排序的链表合并，那么所有链表都合并了
比较次数和交换（或移动）次数 这一节和下一节讲的都是基于比较的排序算法。基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。...冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。 第二，冒泡排序是稳定的排序算法吗 ？...这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。实际上，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。...归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。 归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。...希尔排序过程中，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为 O(1) 。所以，希尔排序是原地排序算法。 第二，希尔排序是稳定的排序算法吗 ？
c为加入元素的个数，排序复杂度是O(zlogz)，加入c次排序就需要排序c次。...合并K个升序链表 (hard)给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。...，每次归并不断合并两个有序链表，直到合并完所有分治后的链表复杂度：时间复杂度O(n * logk)，n是每个链表节点数，k个链表个数，每次归并，链表数量较少一半，复杂度是O(logk)，将两个链表合并成一个顺序链表复杂度是...lists.length) { return null; } // 合并两个排序链表 const merge = (head1, head2) => { let...个排序链表，可以分成两部分，前k/2个链表和后k/2个链表 // 如果将这前k/2个链表和后k/2个链表分别合并成两个排序的链表，再将两个排序的链表合并，那么所有链表都合并了
用队列实现栈 (easy) 方法1.使用两个 Queue 实现 思路：还是考察栈和队列的熟悉程度，没有什么具体的工程实际意义，可以用两个队列来实现栈的功能，但是一个队列的数据导入另一个队列顺序还是没有改变...合并K个升序链表 (hard) 方法1.分治 ds_33 思路：自底而上归并，第一次归并2个链表，第二次归并4个链表......，每次归并不断合并两个有序链表，直到合并完所有分治后的链表 复杂度：时间复杂度O(n * logk)，n是每个链表节点数，k个链表个数，每次归并，链表数量较少一半，复杂度是O(logk)，将两个链表合并成一个顺序链表复杂度是...lists.length) { return null; } // 合并两个排序链表 const merge = (head1, head2) => {...个排序链表，可以分成两部分，前k/2个链表和后k/2个链表 // 如果将这前k/2个链表和后k/2个链表分别合并成两个排序的链表，再将两个排序的链表合并，那么所有链表都合并了
利用双指针技巧，则可以在遍历的过程中同时完成交换元素的操作，时间复杂度降低为 O(1)： 图片 相同类型的题目还有： 【345. 反转字符串中的元音字母】 四、141....在链表这种数据结构中，采用前文所说的前后指针并不一定有效（例如单向链表），这种情况下，双指针的表现形式为：快慢指针。 快慢指针指的是：设置两个前进方向相同但速度不同的指针。 ...本题中，设置每次移动一个单位的慢指针和每次移动两个单位的快指针，那么他们必定会在环内相遇： 图片 相同类型的题目还有： 【26. 删除排序数组中的重复项】 五、125....验证回文串 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。 ...本系列文章会分别给出一种算法的3种难度的总结篇（简单难度，中等难度以及困难难度）。在简单难度中，会介绍该算法的基本知识与实现，另外两个难度，着重讲解解题的思路。
04:在节点2之后插入也是如此。 前提条件：链表 删除，和插入操作，必须清楚前面一个节点，才能保证整个链表不被破坏。...偶数的根本不需要移动，自然就关联在一起了。 思路原地翻转， 步骤1 case1 为例子 奇数移动到前面，需要3个指针 当前指针和 当前指前面一个指针。.../** * 借助三个辅助指针完成单链表翻转 * 注意：这里是原地翻转，不需要建立新的节点。...//因此我可以放心的默认第一个节点是已经排序号的。...排序链表(自习室无声音思路版本)
1、数据：数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。...数据项是数据的不可分割的最小单位 2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算 3、主要的数据存储方式：顺序存储结构（逻辑和物理相邻，存储密度大）和链式存储结构 顺序存储结构： 顺序存储计算公式...5、链表：线性链表（单链表和双向链表等等）和非线性链表 线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。...（注意结点的插入和删除操作） 6、栈：“后进先出”(LIFO)表。栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等 7、队列：“先进先出”线性表。...应用：树的层次遍历 8、串：由零个或多个字符组成的有限序列。
今天我就给你介绍另外一种排序算法，归并排序算法。它的时间复杂度是 , 而且是稳定的排序算法，唯一美中不足的一点是它不是原地排序算法，需要使用额外的存储空间。...没错，归并排序算法一般都是基于递归进行实现的。 好了，接下来，看下动画演示。 代码实现 #!...，合并两个有序数组的操作同样是非常经典的，而且在面试求职过程中会经常用到的。...归并排序里面是合并两个有序的数组，还可以合并两个有序的链表、合并 k 个链表等等。 LeetCode 上具体的题目链接有： 88. 合并两个有序数组 1669. 合并两个链表 21....合并两个有序链表 23. 合并K个升序链表 总结 归并排序是非常高效的排序算法。 时间复杂度数 ,无论要排序的数据是什么样的，性能都是稳定的。
这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。实际上，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。...在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。所以，归并排序不是原地排序算法。...归并排序虽然是稳定的、时间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。 归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。...快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。 4. 希尔排序（Shell Sort） 思想 先将整个待排序的记录序列分割成为若干子序列。...希尔排序过程中，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为 O(1) 。所以，希尔排序是原地排序算法。 第二，希尔排序是稳定的排序算法吗 ？
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
