歸並排序我在之前已經講過了,並且給了在數組的數列的情況下的歸並排序方法,而排序的時間復雜度為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. // #includeusing 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; }