本节主要阐述自顶向下与自底向上的归并排序，以及改变连接状态与改变节点值的可快速排序。下面来仔细阐述。
归并排序是最适合单链表排序的算法，因为两个链表的归并比较简单，和数组的归并过程思路相同。
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个节点的值）。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/175466.html