STL庫list::sort()實現深度解析

list模板的定義以及一些基本成員函數的實現這裡我就不贅述了，還不清楚的同學可以到網上查找相關資料或者直接查看侯捷翻譯的《STL源碼剖析》相應章節。我之所以寫這篇筆記是因為當時看到list::sort()源碼時一時沒看懂，後來在VS項目裡一步步跟蹤數據變化發現了其中的奧秘，被其簡潔高效的非遞歸歸並排序的實現方法所震撼(侯捷在《STL源碼剖析》上注釋說此sort實現使用了快排，應該是弄錯了),下面直接進入主題。

STL源碼剖析簡體中文完整版(高清晰掃描帶目錄)PDF http://www.linuxidc.com/Linux/2016-04/129761.htm

list::sort() 源碼(摘自《STL源碼剖析》)

template <class T, class Alloc>
void list<T, Alloc> :: sort(){
    // 判斷鏈表是否為空或者只有一個元素
    if(node->next == node || link_type(node->next)->next == node){
        return;
    }
    
    list<T, Alloc> carry;
    list<T, alloc> counter[64];
    int fill = 0;
    while(!empty()){
        carry.splice(carry.begin(), *this, 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]);
    }
    swap(counter[fill-1]);
}

以上源碼咋一看並沒有發現元素大小比較的地方，但仔細一看便發現其使用了list的merge成員函數，這個函數功能是合並兩個非減有序鏈表為一個非減有序鏈表，結果為調用該函數的對象。顯然，sort函數的實現使用了歸並排序。為了能在vs下調試跟蹤數據變化，我新建了一個list.sort()的等價外部實現函數。

list.sort()的等價外部實現

void sortList(list<int> &a) {
    if(a.size() <= 1){
        return;
    }
    
    list<int> carry;       // 輔助鏈表，用於從a中提取元素以及臨時保存兩個鏈表的合並結果
    list<int> counter[64]; // 保存著當前每一個歸並層次的結果, i號鏈表保存的元素個數為2的i次方或者0
    int fill = 0;          // 表示當前最大歸並排序的層次，while循環之後fill變成log2(a.size())
    
    while (!a.empty()) {
        carry.splice(carry.begin(), a, a.begin()); // 將鏈表a中的第一個元素移動至carry開頭
        int i = 0;
        // 從小往大不斷合並非空歸並層次直至遇到空層或者到達當前最大歸並層次
        while (i < fill && !counter[i].empty()) {  
            counter[i].merge(carry);    // 鏈表合並，結果鏈表是有序的，必須保證合並前兩個鏈表是有序的
            carry.swap(counter[i++]);   // 鏈表元素互換
        }
        carry.swap(counter[i]);
        if (i == fill) {       // i到達當前最大歸並層次，說明得增加一層
            ++fill;
        }
    }
    
    for (int i = 1; i < fill; ++i) {  // 將所有歸並層次的結果合並得到最終結果counter[fill - 1]
        counter[i].merge(counter[i - 1]);
    }
    a.swap(counter[fill - 1]);
}

算法的巧妙之處在於外層while循環下counter鏈表數組的維護，下面我們就用例子a(8, 6, 520, 27, 124, 214, 688, 12, 36 )來跟蹤counter的變化。事先約定，null表示list不含元素，下面所說的第i次循環之後均指外層while的。a的元素個數為9，歸並層次最多到達第4層，故counter[3]之後的就不顯示了, 它們的值均為null。

第i次循環之後counter[0]counter[1]counter[2]counter[3] 0 8 null null null 1 null 6,8 null null 2 520 6.8 null null 3 null null 6,8,27,520 null 4 124 null 6,8,27,520 null 5 null 124,214 6,8,27,520 null 6 688 124,214 6,8,27,520 null 7 null null null 6,8,12,27,124,214,520,688 8 36 null null 6,8,12,27,124,214,520,688

前3次循環的具體運行過程如下：

• 第0次外層循環，carry取得a列表頭元素8，i == fill == 0 無法進入內層循環，之後carry與counter[0]交換，counter[0] 變為8， fill變為1；
• 第1次外層循環， carry取得a列表頭元素6，counter[0]不為空故進入內層循環，合並carry和counter[0]，內層一次循環之後counter[0]變為null， carry變為(6,8), i == fill == 1退出內層循環。然後carry與counter[1]交換，最後counter[1]變為(6, 8), fill 變為2；
• 第2次外層循環， carry取得a列表頭元素520，counter[0]為空無法進入內層循環，之後carry與counter[0]交換，counter[0] 變為520， fill的值不變；
• 第3次外層循環，carry取得a列表頭元素27，進入內層while循環，先是發現counter[0]不為空，故與其合並，合並之後carry變為(27, 520), counter[0]變為null，然後進入下一次內層循環發現counter[1]不為空，故與其合並，合並之後carry變為(6,8,27,520)， counter[1]變為null，i == fill == 2退出內層循環。最後carry與counter[2]互換，counter[2]變為(6,8,27,520)，fill變為3.

之後的循環過程類似，最後將counter[0]至counter[8]的結果合並即為結果。此算法的時間復雜度為O(N*logN)，空間復雜度為O(N).

總結

傳統歸並排序使用先二分後調用遞歸函數的步驟，應用對象主要是普通數組和vector數組，這兩者的共同點在於可以在O(1)的時間內找到中點。但分析list數據結構可知，尋找其中點需要O(N)復雜度，故不大適合使用傳統歸並排序的思想。後來不知哪位牛人想到了利用二進制的進位思想，結合一個list數組保存各個歸並層次的結果，最終實現了非遞歸版的歸並排序，此想法也可以用在普通數組和vector數組上，具體實現以後有時間再寫。

附調試完整代碼

#include <iostream>
#include <list>
using namespace std;

// list<T>.sort()等價外部實現，用到了歸並排序的算法思想
void sortList(list<int> &a) {
    if(a.size() <= 1){
        return;
    }
    
    list<int> carry;       // 輔助鏈表，用於從a中提取元素以及臨時保存兩個鏈表的合並結果
    list<int> counter[64]; // 保存著當前每一個歸並層次的結果, i號鏈表保存的元素個數為2的i次方或者0
    int fill = 0;          // 表示當前最大歸並排序的層次，while循環之後fill變成log2(a.size())
    
    while (!a.empty()) {
        carry.splice(carry.begin(), a, a.begin()); // 將鏈表a中的第一個元素移動至carry開頭
        int i = 0;
        // 從小往大不斷合並非空歸並層次直至遇到空層或者到達當前最大歸並層次
        while (i < fill && !counter[i].empty()) {  
            counter[i].merge(carry);    // 鏈表合並，結果鏈表是有序的，必須保證合並前兩個鏈表是有序的
            carry.swap(counter[i++]);   // 鏈表元素互換
        }
        carry.swap(counter[i]);
        if (i == fill) {       // i到達當前最大歸並層次，說明得增加一層
            ++fill;
        }
    }
    
    for (int i = 1; i < fill; ++i) {  // 將所有歸並層次的結果合並得到最終結果counter[fill - 1]
        counter[i].merge(counter[i - 1]);
    }
    a.swap(counter[fill - 1]);
}

int main() {
    list<int> test;
    test.push_back(8);
    test.push_back(6);
    test.push_back(520);
    test.push_back(27);
    test.push_back(124);
    test.push_back(214);
    test.push_back(688);
    test.push_back(12);
    test.push_back(36);
    cout << "排序前" << endl;
    for (auto i = test.begin(); i != test.end(); i++) {
        cout << *i << " ";
    }
    cout << endl << "排序後：" << endl;
    sortList(test);
    for (auto i = test.begin(); i != test.end(); i++) {
        cout << *i << " ";
    }
    cout << endl;

    return 0;
}