《链表算法：浅谈并实现一下链表各种排序算法及其性能》

链表排序前置知识阅读本篇前你需要掌握:链表基础至少一种数组排序算法合并两个有序链表的写法这是归并排序的基础组件测试链接:力扣:排序链表、力扣补充:链表的插入排序本篇内容三种链表排序:选择排序:把数组版选择排序的思路迁移到链表上熟悉链表 coding。归并排序递归版:分治写法但不是最优解系统栈会带来O ( log ⁡ n ) O(\log n)O(logn)的空间开销。归并排序迭代版:链表上最强的排序。比较排序中同时拥有O ( n log ⁡ n ) O(n \log n)O(nlogn)时间、O ( 1 ) O(1)O(1)空间、并保持稳定。数组的迭代版快速排序做不到稳定。拓展部分:冒泡排序、插入排序、快速排序的链表写法。为什么希尔排序和堆排序不适合链表。这两个没有实现代码因为性能太差。迭代版归并排序和链表快速排序两节还没写完后续补上。选择排序时间复杂度O ( n 2 ) O(n^2)O(n2)空间复杂度O ( 1 ) O(1)O(1)。先复习数组版本:// 数组中交换i和j位置的数publicstaticvoidswap(int[]arr,inti,intj){inttmparr[i];arr[i]arr[j];arr[j]tmp;}// 选择排序publicstaticvoidselectionSort(int[]arr){if(arrnull||arr.length2){return;}for(intminIndex,i0;iarr.length-1;i){minIndexi;for(intji1;jarr.length;j){if(arr[j]arr[minIndex]){minIndexj;}}swap(arr,i,minIndex);}}数组版思路:假设数组有 n 个元素只需要排前 n-1 个。[0, i-1]是已排序部分[i, n-1]是未排序部分。每轮从未排序部分选出最小值的下标与i位置交换。链表版本的做法:初始时已排序链表为空整个原链表是未排序部分。第一轮从未排序部分找出最小节点作为已排序链表的头节点。之后每轮从未排序部分找出最小节点从原链表中摘除尾插到已排序链表的尾部。原链表遍历完后这个新头节点就是排序后的链表头。classSolution{// 返回未排序链表中最小节点的前驱节点若最小节点是头则返回 nullpublicListNodegetSmallestNode(ListNodehead){ListNodesmallNodehead;ListNodesmallPrevnull;ListNodeprevhead,curhead.next;while(cur!null){if(cur.valsmallNode.val){smallPrevprev;smallNodecur;}prevcur;curcur.next;}returnsmallPrev;}publicListNodesortList(ListNodehead){if(headnull||head.nextnull){returnhead;}ListNodetailnull;// 已排序部分的尾节点ListNodecurhead;// 遍历未排序部分ListNodesmallPrevnull;ListNodesmallNodenull;while(cur!null){smallNodecur;smallPrevgetSmallestNode(cur);if(smallPrev!null){smallNodesmallPrev.next;smallPrev.nextsmallNode.next;}// 如果最小节点就是 curcur 要前进否则 cur 不动cur(cursmallNode)?cur.next:cur;if(tailnull){headsmallNode;}else{tail.nextsmallNode;}tailsmallNode;}returnhead;}}getSmallestNode返回的是最小节点的前驱不是最小节点本身。这样做是为了在外层方法里能直接通过smallPrev.next smallNode.next把它摘下来。如果最小节点本身就是传入的head前驱不存在返回null,外层据此走另一个分支。外层sortList用tail维护已排序链表的尾。第一次进入循环时tail null,把摘出的最小节点设为新的head,之后每次都接到tail后面。归并排序:递归版本对照数组的归并排序链表版本的差异主要在两个地方:空表和单节点直接返回head,不需要处理。数组通过mid划分区间链表没有下标用快慢指针找中点。找到后用prevSlow.next null把链表断成两段独立的链表分别递归。合并两段有序链表因为可能换头要返回新链表的头节点。如果你已经做过链表中点和合并两个有序链表,这一题就是把两者拼起来。// 提交时改类名为 SolutionpublicclassMergeSortRecList{publicstaticListNodesortList(ListNodehead){if(headnull||head.nextnull){returnhead;}// 快慢指针找中点。注意初始化:fast 从 head.next.next 开始ListNodefasthead.next.next;ListNodeslowhead.next;ListNodeprevSlowhead;while(fast!nullfast.next!null){prevSlowslow;slowslow.next;fastfast.next.next;}// 断成两段prevSlow.nextnull;headsortList(head);slowsortList(slow);returnmergeTwoLists(head,slow);}publicstaticListNodemergeTwoLists(ListNodeheadA,ListNodeheadB){ListNodedummynewListNode(Integer.MIN_VALUE);ListNodetaildummy;while(headA!nullheadB!null){if(headA.valheadB.val){tail.nextheadA;headAheadA.next;}else{tail.nextheadB;headBheadB.next;}tailtail.next;}tail.next(headA!null)?headA:headB;returndummy.next;}}时间复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn),空间复杂度O ( log ⁡ n ) O(\log n)O(logn),具备稳定性。链表不支持随机访问找中点要用快慢指针这一步是O ( n ) O(n)O(n),比数组找中点慢。空间开销主要来自系统栈,这也是它不是最优解的原因——迭代版本可以把空间压到O ( 1 ) O(1)O(1)。补充:插入排序插入排序:链表分为已排序部分和未排序部分。cur遍历未排序部分每次拿到一个节点从已排序部分的头开始找它的合适位置p。还需要prev和next。prev始终是cur的前驱执行插入时要把cur摘出去:prev.next next。然后把cur插到p和p.next之间。链表插入排序和数组版本的差异来自数据结构本身。数组取元素是直接读链表要修改前后指针完成摘除。数组插入要整体挪元素链表只需要改两个指针。链表是单向的找位置只能从头开始;数组有连续性和双向访问所以能衍生出折半插入排序之类的优化。头节点要特殊处理。cur有可能比当前所有已排序节点都小需要插到表头。可以用虚拟头节点回避分类讨论。下面两份代码分别给出了用 dummy 和不用 dummy 的写法。插入排序这道题排行榜上 100% 的解法实际上是用归并排序写的所以这一题用插入排序拿不到极致性能正常即可。// 提交时改类名为 Solution并把方法名改成力扣给定的 insertionSortListpublicclassInsertionSortList{// 写法一:用虚拟头节点publicstaticListNodesortList1(ListNodehead){if(headnull||head.nextnull){returnhead;}ListNodecurhead.next,prevhead;ListNodepnull;// 在已排序部分中寻找插入位置ListNodenextnull;ListNodedummynewListNode(Integer.MAX_VALUE);dummy.nexthead;while(cur!null){if(prev.valcur.val){// 已经有序cur 前进prevcur;curcur.next;}else{nextcur.next;// 从 dummy 开始找第一个 p.next.val cur.val 的位置pdummy;while(p.next!nullp.next.valcur.val){pp.next;}// 摘 curprev.nextnext;// 插入到 p 和 p.next 之间cur.nextp.next;p.nextcur;curnext;}}returndummy.next;}// 写法二:不用虚拟头节点对头插情况单独处理publicstaticListNodesortList(ListNodehead){if(headnull||head.nextnull){returnhead;}ListNodecurhead.next,prevhead;ListNodepnull;while(cur!null){if(cur.valprev.val){prevcur;curcur.next;}else{ListNodenextcur.next;if(cur.valhead.val){// cur 比头还小插到表头prev.nextnext;cur.nexthead;headcur;curnext;}else{// 一般情况:在已排序部分找插入位置phead;while(p.next!nullp.next.valcur.val){pp.next;}// 循环结束:p.val cur.val p.next.valprev.nextnext;cur.nextp.next;p.nextcur;curnext;}}}returnhead;}}两份代码的差别只在头插的处理:dummy 把插到表头和插到中间统一成同一种操作代价是多一个虚拟节点;不用 dummy 就要写两个分支。补充:冒泡排序链表冒泡排序比数组版本要烦,因为光记两两交换是不够的——链表里交换意味着改四个指针。数组冒泡有一种常见的优化:用一个标志记录本轮是否发生过交换没交换就提前退出。链表版本可以直接用这个标志作为外层循环的退出条件不需要预先统计长度。publicclassBubbleSortList{publicListNodebubbleSortList(ListNodehead){if(headnull||head.nextnull){returnhead;}booleanisSwap;do{isSwapfalse;ListNodecurhead;ListNodeprevnull;ListNodenexthead.next;while(next!null){if(cur.valnext.val){isSwaptrue;if(prevnull){// 交换的是头节点headnext;cur.nextnext.next;next.nextcur;}else{prev.nextnext;cur.nextnext.next;next.nextcur;}// cur 没动它现在变成了原 next 的后继prevnext;nextcur.next;}else{prevcur;curnext;nextnext.next;}}}while(isSwap);returnhead;}}需要注意交换之后指针的更新方向。交换后cur没动但它在链表中的逻辑位置变了——它现在排在原本的next后面。所以下一轮比较的对象是cur.next。不交换时prev、cur、next三者一起前进。希尔排序不适合链表希尔排序的核心是分组插入排序:用逐步减小的步长 gap 对数组分组排序gap 收敛到 1 时退化为普通插入排序。这依赖数组的随机访问。访问间隔元素的代价不一样。数组里访问第i g a p i gapigap个元素是O ( 1 ) O(1)O(1),链表只能从头遍历是O ( g a p ) O(gap)O(gap)。链表也不需要这个优化。希尔排序在链表上要反复花O ( g a p ) O(gap)O(gap)去找间隔元素本质上是用更高的访问成本去做链表插入排序原本就能做的事情。链表上的希尔排序时间复杂度是O ( n 2 ) O(n^2)O(n2),比直接做链表插入排序还慢。所以你可以认为:链表上不存在希尔排序。堆排序不适合链表堆排序依赖完全二叉树而完全二叉树用数组存储天然契合。一句话概括:越是依赖数组特性的排序越不适合链表。数组强在查询链表强在增删。索引依赖。堆排序的全部操作建立在父节点下标i ii、左孩子2 i 1 2i12i1、右孩子2 i 2 2i22i2的关系上。父子之间的跳转在数组里是O ( 1 ) O(1)O(1)。链表没有下标要么从头遍历找到对应位置要么自己维护一套编号——前者效率太低后者本质上是在链表上模拟数组。上浮下沉的开销。堆排序频繁交换父子节点的位置。链表交换两个节点既要不破坏其它指针关系又要承担前面说的索引查找成本。这两件事叠在一起让堆排序在链表上的实际开销远超数组版本。总结链表排序里真正值得记的只有两个:插入排序和归并排序,其中迭代版归并排序是链表上最强的排序。判断一个数组排序算法能不能迁移到链表看它依赖什么:依赖遍历和频繁插入删除的(选择、归并、冒泡、插入),都有对应的链表版本。依赖随机访问的(希尔、堆),在链表上要么实现不出来要么实现出来性能太差可以视为不存在。