STL中list链表的sort算法详解

今天在学习侯捷先生的《STL源码剖析》这本书，在讲到list链表中的sort算法时，书上写的不详细，很难在短时间内搞明白，我也花了好长时间才搞懂这个算法，下面我就来讲一讲这个算法的实现细节。

附代码如下：

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+1]);

}

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不能使用STL算法sort（），必须使用自己的sort（） member function.因为STL算法sort（）只接受RamdonAccessIterator，在这个函数中采用了快速排序。

详细分析如下：

(1) if(node->next==node || link_type(node->next)->next==node)

这个用来判断是否是空表或者仅有一个元素，如果是其中之一，就不进行任何操作

(2)list<T,Alloc> carry;

list<T,Alloc> counter[64];

这两个是新定义的lists，作为中介数据存放区。

但是list<T,Alloc> counter[64]作为中转是怎么工作的呢？

                counter[0]里存放2的(0+1)次方个元素
             counter[1]里存放2的(1+1)次方个元素
             counter[2]里存放2的(2+1)次方个元素
             counter[3]里存放2的(3+1)次方个元素，依次类推

数据中转原则是：当第i个元素即counter[i]的内容个数等于2的(i+1)次方时，就要把counter[i]的数据转移给counter[i+1].

举个例子：假设list里面等待排序的元素为：21,45,1,30,52,3,58,47,22,59,0,58.

具体过程如下：

取出第1个数21，放到__counter[0]里，这时__counter[0]里有一个元素，小于2，继续

counter[0]: 21

counter[1]: NULL

取出第2个数45，放到counter[0]里(不是简单的放，而是排序放，类似两个list做merge)，这时counter[0]里有2个元素了，需要把这两个元素转移到counter[1].

counter[0]: NULL

counter[1]: 21,45

取出第3个数1，放到counter[0]里，count[0]与count[1]都小于规定个数

counter[0]: 1

counter[1]: 21,45

取出第4个数30，放到counter[0]里，这时counter[0]的个数等于2了，需要转移到counter[1]里

counter[0]: NULL

counter[1]: 1,21,30,45

但这时counter[1]里的个数又等于4了，所有需要把counter[1]的值转移到counter[2]里，

counter[0]: NULL

counter[1]: NULL

counter[2]: 1,21,30,45

然后取出52，放入counter[0]

counter[0]: 52

counter[1]: NULL

counter[2]: 1,21,30,45

然后取出3，放入counter[0]

counter[0]: 3,52

counter[1]: NULL

counter[2]: 1,21,30,45

这时候需要转移

counter[0]: NULL

counter[1]: 3,52

counter[2]: 1,21,30,45

然后取58

counter[0]: 58

counter[1]: 3,52

counter[2]: 1,21,30,45

然后取47

counter[0]: 47,58

counter[1]: 3,52

counter[2]: 1,21,30,45

需要转移

counter[0]: NULL

counter[1]: 3,47,52,58

counter[2]: 1,21,30,45

还需要转移

counter[0]: NULL

counter[1]: NULL

counter[2]: 1,3,21,30,47,45,52,58

还需要转移

counter[0]: NULL

counter[1]: NULL

counter[2]: NULL