程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 算法學習 - 鏈表之歸並排序_O(1)空間_O(NlogN)時間_C++

算法學習 - 鏈表之歸並排序_O(1)空間_O(NlogN)時間_C++

編輯:C++入門知識

算法學習 - 鏈表之歸並排序_O(1)空間_O(NlogN)時間_C++


歸並排序

歸並排序我在之前已經講過了,並且給了在數組的數列的情況下的歸並排序方法,而排序的時間復雜度為O(NlogN).想看的話鏈接如下:
歸並排序,快排,冒泡排序

但是這個歸並排序有一個缺點:需要O(n)的額外空間。

那麼這個缺點在什麼情況下會解決呢?就是數列是以鏈表形式存儲的時候!就不需要額外的申請O(n)級別的空間。

那麼我們為什麼要用歸並排序呢? 不是還有快排,堆排麼?都是速度很快的排序。其實在鏈表中是不適合的!因為在快排的時候,查找標桿是O(1)級別的,但是在鏈表中只能得到head節點,得到標桿需要O(n)級別的。那麼復雜度就上升到(nnlogn)級別的了。

代碼實現

所以在鏈表的情況下需要使用歸並排序,復雜度NlogN, 而且不需要申請額外空間。

//
//  main.cpp
//  MergeList
//
//  Created by Alps on 14/12/6.
//  Copyright (c) 2014年 chen. All rights reserved.
//

#include 
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x),next(NULL){}
};

class Solution{
public:
    ListNode *sortList(ListNode* head){
        if (head == NULL || head->next == NULL) {
            return head;
        }
        
        ListNode* mid = getMid(head);
        ListNode* right = NULL;
        if (mid != NULL) {
            right = mid->next;
            mid->next = NULL;
        }
        head = sortList(head);
        right = sortList(right);
        head = MergeList(head, right);
        return head;
    }
    
    ListNode* getMid(ListNode* node){
        if (node == NULL || node->next == NULL) {
            return node;
        }
        ListNode* l1 = node;
        ListNode* l2 = node->next;
        while (l2 && l2->next) {
            l1 = l1->next;
            l2 = l2->next->next;
        }
        return l1;
    }
    
    ListNode* MergeList(ListNode* left, ListNode* right){
        if (left == NULL) {
            return right;
        }
        if (right == NULL) {
            return left;
        }
        ListNode* temp = NULL;
        if (left->val >= right->val) {
            temp = right->next;
            right->next = left;
            left = right;
            right = temp;
        }
        left->next = MergeList(left->next, right);
        return left;
    }
};

int main(int argc, const char * argv[]) {
    Solution sl;
    ListNode *head = new ListNode(4);
    head->next = new ListNode(2);
    head->next->next = new ListNode(1);
    head->next->next->next = new ListNode(3);
    sl.sortList(head);
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved