### 前言 ? 由于STL本身的排序算法sort接受的輸入迭代器是隨機訪問迭代器，但是雙向list鏈表容器的訪問方式是雙向迭代器，因此，不能使用STL本身的排序算法sort，必須自己定義屬于自己訪問的排序算法。我們從源碼的剖析中，可以看到該排序算法思想類似于歸并排序。 ### list容器之排序算法sort ? 在該排序算法的實現過程中，定義了一個類似于搬運作用的鏈表carry和具有中轉站作用的鏈表counter，這里首先對counter[i]里面存儲數據的規則進行分析；counter[i]里面最多存儲數據個數為[](http://www.codecogs.com/eqnedit.php?latex=2^{(i+1)})，若存儲數據超過該數字，則向相鄰高位進位，即把counter[i]鏈表里的內容都合并到counter[i+1]鏈表。carry負責取出原始鏈表的頭一個數據節點和交換數據中轉站作用；源碼中的fill表示當前可處理數據的個數為[](http://www.codecogs.com/eqnedit.php?latex=2^{(fill)})。下面給出sort的源碼分析： ~~~ //按升序進行排序，list鏈表的迭代器訪問時雙向迭代器 //因為STL的排序算法函數sort()是接受隨機訪問迭代器，在這里并不適合 template <class _Tp, class _Alloc> void list<_Tp, _Alloc>::sort() { // Do nothing if the list has length 0 or 1. if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) { list<_Tp, _Alloc> __carry;//carry鏈表起到搬運的作用 //counter鏈表是中間存儲作用 /* *其中對于counter[i]里面最多的存儲數據為2^(i+1)個節點 *若超出則向高位進位即counter[i+1] */ list<_Tp, _Alloc> __counter[64]; int __fill = 0; while (!empty()) {//若不是空鏈表 //第一步： __carry.splice(__carry.begin(), *this, begin());//把當前鏈表的第一個節點放在carry鏈表頭 int __i = 0; while(__i < __fill && !__counter[__i].empty()) { //第二步： __counter[__i].merge(__carry);//把鏈表carry合并到counter[i] //第三步： __carry.swap(__counter[__i++]);//交換鏈表carry和counter[i]內容 } //第四步： __carry.swap(__counter[__i]);//交換鏈表carry和counter[i]內容 //第五步： if (__i == __fill) ++__fill; } for (int __i = 1; __i < __fill; ++__i) //第六步： __counter[__i].merge(__counter[__i-1]);//把低位不滿足進位的剩余數據全部有序的合并到上一位 //第七步： swap(__counter[__fill-1]);//最后把已排序好的鏈表內容交換到當前鏈表 } } ~~~ ? 從源碼中，我們可以看到，第一個while循環執行的條件是當前鏈表必須非空，該算法的核心就是while里面的處理，嵌套while(即第二個while)執行的條件是i小于fill且counter[i]鏈表是非空；下面給出實例進行分析，在分析之前先做一些規定： 1. 把第20行語句carry.splice(carry.begin(), *this, begin())標記為下圖中執行的步驟1； 1. 把第25行語句counter[i].merge(carry)標記為下圖中執行的步驟2； 1. 把第27行語句carry.swap(counter[i++])標記為下圖中執行的步驟3； 1. 把第30行語句carry.swap(counter[i])標記為下圖中執行的步驟4； 1. 把第32行語句if (i == fill) ++fill標記為下圖中執行的步驟5； 1. 把第37行for循環里面語句counter[i].merge(counter[i-1])標記為下圖中執行的步驟6； 1. 把第39行最后一個語句swap(counter[fill-1])標記為下圖中執行的步驟7； ? 下圖是待排序的原始鏈表：  ? 下面是排序算法sort的執行過程，定義初始值fill=0，因為原始鏈表有四個節點，即原始鏈表非空，則執行while循環里面的語句：注：由于方便畫圖，下面相鄰方塊之間表示是雙向鏈表的連接；白色的方塊表示空鏈表； ?**第一次執行**while**循環：**步驟1搬運鏈表carry取出當前鏈表的第一個數據節點7，初始值i=0，由于嵌套while循環條件不成立，則跳過嵌套while循環，直接進入到步驟4，交換carry和counter[i](i=0)的內容；又因為此時i=fill，則更新值++fill，即fill=1；流圖如下：  **第二次執行**while**循環：**步驟1搬運鏈表carry取出當前鏈表的第一個數據節點5，初始值i=0，由于嵌套while循環條件成立，步驟2將carry鏈表的內容有序的合并到counter[i](i=0)鏈表中，再執行步驟3交換carry和counter[0]內容且i++，此時carry有兩個有序的節點5和7，counter[0]為空鏈表，i的值為i=1；這時嵌套while循環條件不成立；跳轉到步驟4交換carry和counter[1]的內容，且執行步驟5更新fill的值++fill，第二次while循環執行結束時，數據節點的狀況為：carry和counter[0]內容都為空，counter[1]有兩個有序的節點5和7，值fill=2；流圖如下：  ?**第三次執行while循環：**步驟1搬運鏈表carry取出當前鏈表的第一個數據節點8，初始值i=0，由于嵌套while循環條件不成立，則跳過嵌套while循環，直接進入到步驟4，交換carry和counter[i](i=0)的內容；又因為此時i不等于fill，則不更新fill值，即fill=2；第三次while循環執行結束時，數據節點的狀況為：carry為空，counter[0]內容為一個節點8，counter[1]有兩個有序的節點5和7，值fill=2；流圖如下：  ?**第四次執行while循環：**步驟1搬運鏈表carry取出當前鏈表的第一個數據節點1，初始值i=0，由于嵌套while循環條件成立，步驟2將carry鏈表的內容有序的合并到counter[i](i=0)鏈表中，再執行步驟3交換carry和counter[0]內容且i++，此時carry有兩個有序的節點1和8，counter[0]為空鏈表，i的值為i=1；這時嵌套while循環條件依然成立；繼續執行步驟2將carry的內容有序的合并到counter[1]鏈表中，再執行步驟3交換carry和counter[1]的內容且++i，此時，carry內容為四個有序的節點1、5、7和8，counter[0]和counter[1]的內容都為空鏈表，i的值為i=2；這時嵌套while循環條件不成立；跳轉到步驟4交換carry和counter[2]的內容，且執行步驟5更新fill的值++fill，第四次while循環執行結束時，數據節點的狀況為：carry、counter[0]和counter[1]內容都為空，counter[2]有四個有序的節點1、5、7和8，值fill=3；流圖如下：  ? 最后，由于此時當前鏈表為空鏈表，則跳出while循環，執行for語句，因為i=2之前的counter[1]和counter[0]內容都為空，則執行完for語句之后鏈表都沒變化，然后執行步驟7交換當前鏈表和counter[2]的內容，執行完后，counter[2]為空，當前鏈表內容為四個有序的節點1、5、7和8；流程如下：  ? 以上是list排序算法的整個流程，關鍵是要理解其核心，不斷地更新鏈表內容。 ? 參考資料： ? ? ? 《STL源碼剖析》侯捷； ? ? ? 《[STL源碼剖析之list的sort函數實現](http://www.cnblogs.com/wwblog/p/3653055.html)》