「生活可以更简单, 欢迎来到我的开源世界」
序列式容器list的排序算法笔记
2020-05-28
C++

序列式容器list的排序算法笔记

list 不能使用STL算法sort(),因为STL的sort函数要求random_access_iterator,而list的迭代器是bidirectional_iterator,所以必须使用自己的成员函数sort()。

SGI STL的list_sort使用的是非递归的归并排序,先将前两个元素归并,再将后两个元素归并,归并这两个小子序列成为4个元素的有序子序列;重复这一过程,得到8个元素的有序子序列,16个的,32个的……,直到全部处理完。

为何list不使用普通的merge_sort呢?这比较好理解,因为每次找到中间元素再一分为二的代价实在太大了,不适合list这种非random_access_iterator的容器。

该排序算法主要调用了swap()和merge(),而这些又依赖于内部实现的transfer()(其时间代价为O(1))。该算法时间代价亦为n*log(n):分析代码可以发现,代码使用了64个list暂存部分有序list_node,将list总共分成n个有序list,第n个list存的node数量要么为0要么为$2^n$。

template <class T, class Alloc>
void list<T, Alloc>::sort(){
//如果元素个数小于等于1,直接返回
if(node->next == node || link_type(node->next)->next == node)
return;
// 保存下层merge返回的结果
list<T, Alloc> carry;
// 模拟merge sort使用的堆栈,保存部分有序的list
// 64应该写作sizeof(size_type) * 8,即最大的递归调用层次。
list<T, Alloc> counter[64];
// 指示堆栈层次
int fill = 0;
while(!empty()){
// 将begin处的元素从list取下,insert到carry中
carry.splice(carry.begin(), *this, begin());
int i = 0;
while(i < fill && !counter[i].empty()){
//将carry中的元素合并到counter[i]中,然后carry变为空的
counter[i].merge(carry);
//交换之后counter[i-1]为空
carry.swap(counter[i++]);
}
// carry将结果保存到堆栈
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]);
}
}

<⇧>