搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 光城 > ​精益求精单链表归并排序与快速排序

​精益求精单链表归并排序与快速排序

光城 2019-11-08


精益求精单链表归并排序与快速排序

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;

}



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《​精益求精单链表归并排序与快速排序》的版权归原作者「光城」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注光城微信公众号

光城微信公众号:guangcity

光城

手机扫描上方二维码即可关注光城微信公众号

光城最新文章

精品公众号随机推荐