STL 中的鏈表排序

一直以來學習排序算法， 都沒有在鏈表排序上下太多功夫，因為用得不多。最近看STL源碼，才發現，原來即使是鏈表，也能有時間復雜度為O(nlogn)的算法，

大大出乎我的意料之外，一般就能想到個插入排序。

下面的代碼就是按照源碼寫出的（去掉了模板增加可讀性），注意forward_list是C++11新加的單向鏈表，這里選這個是因為它更接近我們自己實現鏈表時的做法。

void sort_list(forward_list<int>& l){auto it = l.begin();if (l.empty() || ++it == l.end())return;forward_list<int> carry;forward_list<int> counter[64];//總共只設立了64個桶，因為第i個桶被填充的時候，里面至多2^i個元素，2^64，遠超一般元素數目int fill = 0; //fill記錄的是當前填到哪個桶了while (!l.empty()){carry.splice_after(carry.cbefore_begin(), l, l.cbefore_begin());//每次從原鏈表上取下一個元素int i = 0;while (i < fill && !counter[i].empty()){counter[i].merge(carry);carry.swap(counter[i++]);}carry.swap(counter[i]);if (i == fill) ++fill;}for (int i = 1; i < fill; ++i)counter[i].merge(counter[i - 1]);l.swap(counter[fill - 1]);
}

　　關于此算法的分析：網上很多爭論這個到底是快速排序還是歸并排序的（侯捷的書上說是快排）。

? ? ? 為了理解這個代碼，可以手動運行一下。

? ? ? fill，記錄用到了幾個桶，最外層循環保證這樣一個事實：從第0個桶到第fill - 1個桶里面，要么為空，要么存儲有2^fill個元素，而且是有序鏈表。

? ? ? 每次與新取下的元素（存儲在carry中）合并的桶都是counter[0]。如果第0個桶里沒有元素，那就直接放進去carry.swap(counter[i])。下一輪循環的

? ? ?時候，因為counter[0]里有元素了，就會進入內層循環，這時候，counter[i].merge(carry)使得第0個桶變為一個含兩個元素的鏈表，然后內層循環第二步，又將這個鏈表

轉移到carry中，下一輪內層循環的時候，帶有兩個元素的carry就會爭取與第1個桶合并（如果第1個桶不空的話），如果第一個桶為空，它將退出內層循環并將元素放進第一個桶，（此時發現i == fill，于是fill變為2）然后下一輪外層循環繼續從鏈表中取下一個元素，（此時counter[0]為空,counter[1]中含有兩個元素），如前面一樣，先是發現counter[0]是空的，進不去內層循環，于是直接把元素填到counter[0]中，下一次外層循環又取一個元素，進入內層循環，與counter[0]合并，交換，然后下一輪內層循環中，帶有兩個元素的carry就會與帶有兩個元素的counter[1]合并，交換, i == fiil == 2退出內層循環，四個元素變到第2個桶中，fill++。

?

?

?

? ? ? ? ? ? ? ? 走完這一遍之后，感覺清晰了，但是除了外層循環的循環不變條件以外，實在是很難從基本的快排或歸并排序的思想中想到這樣去做。