精益求精单链表归并排序与快速排序
精益求精单链表归并排序与快速排序
精益求精单链表归并排序与快速排序
0.导语
本节主要阐述自顶向下与自底向上的归并排序，以及改变连接状态与改变节点值的可快速排序。下面来仔细阐述。
1.自底向上的归并排序
归并排序是最适合单链表排序的算法，因为两个链表的归并比较简单，和数组的归并过程思路相同。
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)
首先编写两个链表的合并程序：
非递归实现
/**
* 非递归合并
* @param l1
* @param l2
* @return
*/
ListNode* __merge(ListNode* l1, ListNode* l2) {
ListNode* dummyHead = new ListNode(0),*p=dummyHead;
while(l1&&l2) {
if(l1->val<l2->val) {
p->next=l1;
p=l1;
l1=l1->next;
} else {
p->next=l2;
p=l2;
l2=l2->next;
}
}
p->next = l1?l1:l2;
p=dummyHead->next;
delete dummyHead;
return p;
}递归实现
/**
* 递归合并
* @param l1
* @param l2
* @return
*/
ListNode* merge(ListNode* l1,ListNode* l2)
{
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
if(l1->val < l2->val)
{
l1->next=merge(l1->next,l2);
return l1;
}
else
{
l2->next=merge(l2->next,l1);
return l2;
}
}对于链表的归并合并与数组归并合并区别，我们会发现链表不能像数组那样根据index去快速索引到相应位置上的值，那么在对链表进行归并排序的时候，就需要确定那两个列表进行归并，然后调用上述merge进行合并即可。
对于一个链表如下：假设sort1为合并列表1的head，sort2为合并列表2的head，那么我们关键就是找出每次合并的这个head即可。
3 4 5 7 8 10
sort1 sort2因此这里写出一个获取head的函数：其中head为当前传进来的链表头结点，sz为几路归并。
ListNode* getHead(ListNode* head, int sz) {
ListNode* p = head;
while(p&&--sz)
p=p->next;
// 此时p指向的是从head数满足sz个节点的位置
if(!p) return p;
// 返回下一个待归并sort1的头节点
ListNode* next = p->next;
// 断开尾部
p->next=NULL;
return next;
}最后，来编写一下自底向上的归并排序函数：
/**
* 自底向上的归并排序
* @param head
* @return
*/
ListNode* sortList(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* p = head;
int n = 0;
// 获取链表总长度
while (p) {
++n;
p = p->next;
}
for (int sz = 1; sz <= n; sz+=sz) {
ListNode* cur = dummyHead->next;
ListNode* tail=dummyHead;
while(cur) {
ListNode* sort1Head = cur;
ListNode* sort2Head = getHead(sort1Head,sz);
cur = getHead(sort2Head,sz); // left->@->@->@ right->@->@->@...
tail->next = __merge(sort1Head,sort2Head); // left->@->@->@ right->@->@ cur->@->@...
// tail指向合并链表末尾
while(tail->next) {
tail=tail->next;
}
}
}
p=dummyHead->next;
delete dummyHead;
return p;
}2.自顶向下的归并排序
自顶向下的归并排序需要注意的是：如何找到链表的中点？
通过2个快慢指针，快指针每一步走2个节点，慢指针每一步走1个节点，当快指针到达链表尾部时，慢指针到达链表的中间节点。
/**
* 自顶向下的归并排序
* @param head
* @return
*/
ListNode* sortList(ListNode* head) {
return __mergesort(head);
}
ListNode* __mergesort(ListNode* node)
{
if(!node || !node->next) return node;
ListNode *fast=node;//快指针走两步
ListNode *slow=node;//慢指针走一步
ListNode *brek=node;//断点
while(fast && fast->next)
{
fast=fast->next->next;
brek=slow;
slow=slow->next;
}
brek->next=nullptr;
ListNode *l1=__mergesort(node);
ListNode *l2=__mergesort(slow);
//合并[node...brek] [slow...fast]
return merge(l1,l2);
}3.改变链接的快速排序
改变链接的指向思路：
- 将比枢椎（这里选择第一个节点）小的值，链接到一个小于枢椎的链表中；
- 比枢椎大的值，链接到一个大于枢椎的链表中；
- 将小于枢椎值的链表，枢椎节点，大于枢椎值的链表链接起来。
对一段链表执行划分过程时，头节点可能发生改变以及终止节点可能是非空的，因此对一段链表的划分过程需要给出：前驱节点 。
/**
* 快排(改变链接)
* @param head
* @return
*/
ListNode* sortList(ListNode* head) {
ListNode dummyHead(0);
dummyHead.next=head;
quickSort(&dummyHead, head, NULL);
return dummyHead.next;
}
void quickSort(ListNode* dummyHead, ListNode* head, ListNode* tail) {
if(head!=tail) {
ListNode *pivot = Partation(dummyHead, head);
quickSort(dummyHead, dummyHead->next, pivot);
quickSort(pivot, pivot->next, tail);
}
};
ListNode* Partation(ListNode* dummyHead, ListNode* head) {
int pivot = head->val; // 选第一个节点为枢椎
ListNode nodeL(0), nodeR(0);
ListNode* pleft = &nodeL,* pright = &nodeR,* p = head->next;
while (p) {
if (p->val < pivot) {
pleft->next = p;
pleft = p;
} else {
pright->next = p;
pright = p;
}
p=p->next;
}
// 大于枢椎的链表连接尾部NULL
pright->next = NULL;
// 小于枢椎的链表连接head
pleft->next = head;
// head链接大于枢椎的链表第一个节点
head->next = nodeR.next;
// 更新实际返回链表的头节点指向
dummyHead->next = nodeL.next; // 链表头节点
return head;
};4.改变值的快速排序
改变值的快速排序思想：由于链表只能顺序索引，故不能使用数组划分的方法。将比枢椎小的节点的值，依次和枢椎后的节点的值交换。如 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个节点的值）。
/**
* 快速排序(改变值)
*/
ListNode *partition(ListNode *head){
int pivot = head->val;
ListNode *slow=head, *fast=head->next;
while(fast){
if(fast->val < pivot){
slow = slow->next;
swap(slow->val, fast->val);
}
fast=fast->next;
}
swap(head->val, slow->val);
return slow;
}
void quickSort(ListNode *head, ListNode *tail){
if(head!=tail){
ListNode *pivot = partition(head);
printLinkedList(head);
quickSort(head, pivot);
quickSort(pivot->next, tail);
}
}
ListNode* sortList3(ListNode* head) {
quickSort(head, nullptr);
return head;
}