鏈表排序，可以插入排序，我就不寫了。

實現歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

?

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

第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列

第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置

第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置

重復步驟3直到某一指針超出序列尾

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

數組排序參考

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;}
};

?