快捷導(dǎo)航

C++歸并法+快速排序?qū)崿F(xiàn)鏈表排序的方法

更新時(shí)間：2021年04月20日 09:38:18 作者：秦楓-_-

這篇文章主要介紹了C++歸并法+快速排序?qū)崿F(xiàn)鏈表排序的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

本文主要介紹了C++歸并法+快速排序?qū)崿F(xiàn)鏈表排序的方法，分享給大家，具體如下：

在這里插入圖片描述

我們可以試用歸并排序解決：
對鏈表歸并排序的過程如下。

找到鏈表的中點(diǎn)，以中點(diǎn)為分界，將鏈表拆分成兩個(gè)子鏈表。尋找鏈表的中點(diǎn)可以使用快慢指針的做法，快指針每次移動(dòng) 2 步，慢指針每次移動(dòng) 1步，當(dāng)快指針到達(dá)鏈表末尾時(shí)，慢指針指向的鏈表節(jié)點(diǎn)即為鏈表的中點(diǎn)。

對兩個(gè)子鏈表分別排序。

將兩個(gè)排序后的子鏈表合并，得到完整的排序后的鏈表

上述過程可以通過遞歸實(shí)現(xiàn)。遞歸的終止條件是鏈表的節(jié)點(diǎn)個(gè)數(shù)小于或等于 1，即當(dāng)鏈表為空或者鏈表只包含 1 個(gè)節(jié)點(diǎn)時(shí)，不需要對鏈表進(jìn)行拆分和排序。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sortList(head, nullptr);
    }

    ListNode* mergesort(ListNode* head, ListNode* tail) {
        if (head == nullptr) {
            return head;
        }
        if (head->next == tail) {
            head->next = nullptr;
            return head;
        }
        ListNode* slow = head, * fast = head;
        while (fast != tail) {
            slow = slow->next;
            fast = fast->next;
            if (fast != tail) {
                fast = fast->next;
            }
        }
 
        return merge( mergesort(head, slow),  mergesort(slow, tail));
    }

    ListNode* merge(ListNode* head1, ListNode* head2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* temp = dummyHead, * temp1 = head1, * temp2 = head2;
        while (temp1 != nullptr && temp2 != nullptr) {
            if (temp1->val <= temp2->val) {
                temp->next = temp1;
                temp1 = temp1->next;
            }
            else {
                temp->next = temp2;
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        if (temp1 != nullptr) {
            temp->next = temp1;
        }
        else if (temp2 != nullptr) {
            temp->next = temp2;
        }
        return dummyHead->next;
    }
};

快速排序不能隨機(jī)選取節(jié)點(diǎn)，時(shí)間復(fù)雜度太高所以會超時(shí)

class Solution {
    public static ListNode sortList(ListNode head) {
        return quickSort(head ,null);
    }

    public static ListNode quickSort(ListNode head ,ListNode end){
        if(head ==end || head.next ==end) return head;
        ListNode lhead = head ,utail = head ,p = head.next;
        while (p != end){
            ListNode next = p.next;
            if(p.val < head.val){//頭插
                p.next = lhead;
                lhead = p;
            }
            else { //尾插
                utail.next = p;
                utail = p;
            }
            p = next;
        }
        utail.next = end;
        ListNode node = quickSort(lhead, head);
        head.next =  quickSort(head.next, end);
        return node;
    }
}

到此這篇關(guān)于C++歸并法+快速排序?qū)崿F(xiàn)鏈表排序的方法的文章就介紹到這了,更多相關(guān)C++ 鏈表排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: