链表排序-归并

男娘i 2022-05-08 06:06 254阅读 0赞

链表排序，可以插入排序，我就不写了。

实现归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路[归并][Link 1]。

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经[排序][Link 2]序列之和，该空间用来存放合并后的序列

第二步：设定两个[指针][Link 3]，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

数组排序参考

[https://blog.csdn.net/hebtu666/article/details/81434236][https_blog.csdn.net_hebtu666_article_details_81434236]

快慢指针：快的一次动两个，慢的一次一个，当快的到最后，慢的一定在中间。

自己手动模拟吧

/*
      考点：
      1. 快慢指针；
      2. 归并排序。
      复杂度分析:
                 T(n)            拆分 n/2, 归并 n/2 ，一共是n/2 + n/2 = n
                /    \           以下依此类推：
              T(n/2) T(n/2)      一共是 n/2*2 = n
             /    \  /     \
            T(n/4) ...........   一共是 n/4*4 = n
     
           一共有logn层，故复杂度是 O(nlogn)
     */
    class Solution {
    public:
        ListNode *sortList(ListNode *head) {
            if (!head || !head->next) return head;
             
            ListNode* p = head, *q = head->next;
            while(q && q->next) //快慢指针
            {
                p = p->next;
                q = q->next->next;
            }
             
            ListNode* left = sortList(p->next);//左右重复
            p->next = NULL;
            ListNode* right = sortList(head);
             
            return merge(left, right);
        }
         
         
        ListNode *merge(ListNode *left, ListNode *right) {
            ListNode dummy(0);
            ListNode *p = &dummy;
            while(left && right) {
                if(left->val < right->val) //小的放进来，指针向后
                {
                    p->next = left;
                    left = left->next;
                }
                else 
                {
                    p->next = right;
                    right = right->next;
                }
                p = p->next;
            }
            if (left) p->next = left;//剩下的
            if (right) p->next = right;
            return dummy.next;
        }
    };

[Link 1]: https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6/253741
[Link 2]: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F
[Link 3]: https://baike.baidu.com/item/%E6%8C%87%E9%92%88
[https_blog.csdn.net_hebtu666_article_details_81434236]: https://blog.csdn.net/hebtu666/article/details/81434236