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

2019 年 10 月 6 日
筆記

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

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;  }