【算法】单链表的快速排序和归并排序

清疚 2022-06-01 12:58 243阅读 0赞

当我们要对一个单链表进行排序，并要求复杂度为O(nlgn)时。在对数组排序的算法中，复杂度为O(nlgn)的算法有：快速排序、归并排序和堆排序。由于堆排序需要将数据组织成一个最大堆，这对于链表来说需要将其重新构造为一个二叉树，这样做太过复杂并且浪费额外的空间。所以只能考虑快速排序和归并排序。  
由于单链表不支持对结点的随机访问，所以不能直接套用在数组上的排序算法。由于快速排序和归并排序都包含二分的思想，所以**在链表排序过程中使用快指针和慢指针来完成对链表的二分操作。**

## 快速排序 ##

设有两个指针low和high，两个指针开始时指向首节点，并令基准值key为首节点的值，令指针low前面节点的值小于key，后面的节点大于等于key。将指针high逐个向后移动，每遇到一个节点的值小于key，就将low向后移动一个节点，之后将该high所指节点的值与low交换。当high移动到链表末尾时，将head与low的值交换，这时便完成了对链表的一次二分，head与low->next分别为两个新链表的头节点。之后对两个新链表进行递归操作，直到链表有序。

/**
     * Definition of ListNode
     * class ListNode {
     * public:
     *     int val;
     *     ListNode *next;
     *     ListNode(int val) {
     *         this->val = val;
     *         this->next = NULL;
     *     }
     * }
     */
    void quickSort(ListNode *head, ListNode *end){
        if(head == end || head->next == end)
            return;
        int t, key = head->val;
        ListNode *low = head;
        ListNode *high = head->next;    
        while(high != end){
            if(high->val < key){
                low = low->next;
                t = high->val;
                high->val = low->val;
                low->val = t;
            }
            high = high->next;
        }
    
        head->val = low->val;
        low->val = key;
        quickSort(head, low->next);
        quickSort(low->next, end);
    }

## 归并排序 ##

对于归并排序，我们使用快指针和慢指针：quick和slow 两个指针起始时都指向头节点，然后quick每向后移动两个节点，slow向后移动一个节点。当quick移动到链表末尾时，slow正好指向链表中部的节点，此时就对链表完成了一次二分。对于每个链表都分别对它二分后的两个链表进行归并排序（MergeSort），之后对分别有序的两个链表进行归并（Merge）。

由于会在函数中改变传入的指针的指向，所以这里的函数参数均使用指针的引用，而非直接传递指针。

void MergeSort(ListNode *&head){
        if(head == NULL || head->next == NULL)
            return;
    
        ListNode *slow = head, *quick = head;
            ListNode *pre;
    
        while(quick && quick->next){
            quick = quick->next->next;
            pre = slow;
            slow = slow->next;
        }
        pre->next = NULL;
        ListNode *l, *r;
        MergeSort(head);
        MergeSort(slow);
        Merge(head, slow);
    }
    
    void Merge(ListNode *&l, ListNode *&r){
        ListNode *head = new ListNode(0);
        ListNode *pt = head;
    
        while(l && r){
            if(l->val <= r->val){
                pt->next = l; 
                l = l->next;
                pt = pt->next;
            }
            else{
                pt->next = r;
                r = r->next;
                pt = pt->next;
            }
        }
        if(l)
            pt->next = l;
        if(r)
            pt->next = r;
    
        l = head->next;
        delete head;
    }