单向链表 快速排序（单向链表归并排序）



本节主要阐述自顶向下与自底向上的归并排序，以及改变连接状态与改变节点值的可快速排序。下面来仔细阐述。

归并排序是最适合单链表排序的算法，因为两个链表的归并比较简单，和数组的归并过程思路相同。

bottom-to-up 的归并思路：先两个两个的 merge，完成一趟后，再 4 个4个的 merge，直到结束。

例如：[4,3,1,7,8,9,2,11,5,6].

step=1: (3->4)->(1->7)->(8->9)->(2->11)->(5->6)step=2: (1->3->4->7)->(2->8->9->11)->(5->6)step=4: (1->2->3->4->7->8->9->11)->5->6step=8: (1->2->3->4->5->6->7->8->9->11)

首先编写两个链表的合并程序：

非递归实现

递归实现

对于链表的归并合并与数组归并合并区别，我们会发现链表不能像数组那样根据index去快速索引到相应位置上的值，那么在对链表进行归并排序的时候，就需要确定那两个列表进行归并，然后调用上述merge进行合并即可。

对于一个链表如下：假设sort1为合并列表1的head，sort2为合并列表2的head，那么我们关键就是找出每次合并的这个head即可。

因此这里写出一个获取head的函数：其中head为当前传进来的链表头结点，sz为几路归并。

最后，来编写一下自底向上的归并排序函数：

自顶向下的归并排序需要注意的是：如何找到链表的中点？

通过2个快慢指针，快指针每一步走2个节点，慢指针每一步走1个节点，当快指针到达链表尾部时，慢指针到达链表的中间节点。

改变链接的指向思路：

对一段链表执行划分过程时，头节点可能发生改变以及终止节点可能是非空的，因此对一段链表的划分过程需要给出：前驱节点 。

改变值的快速排序思想：由于链表只能顺序索引，故不能使用数组划分的方法。将比枢椎小的节点的值，依次和枢椎后的节点的值交换。如 5->3->6->4->7->2 则 5 为枢椎3 < 5: swap(3, 3) ，(起始交换位置为基元的下一个节点，即第2个节点) 6 > 5: continue; 4 < 5: swap(6, 4) （交换位置后移，交换4和第3个节点的值） 7 > 5: continue 2 < 5: swap(4, 2) （交换位置后移，交换2和第4个节点的值）

循环结束 swap(5, 2) （交换枢椎值和第4个节点的值）。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/41543.html