STL的算法中,提供了sort()算法,算法接收两个RandomAccessIterator。所有关系型容器底层使用红黑树的,有自动排序功能。序列容器中的stack,queue使用priority-queue。而优先队列使用堆实现,它们都有特定的出入口,不允许排序。剩下的vector,list,deque中,list无法使用,因为list的迭代器属于BidirectionIterators。list是双向链表。

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=0=1;i<fill;++i)

counter[i].merge(counter[i-1]);

swap(counter[fill-1]);


} 



首先这里使用到两个list的函数。



void splice(iterator position,list &,iterator i)

函数将i所指的元素结合于position所指的位置之前。



template<class T,class Alloc>

void list<T,Alloc>::merge(list<T,Alloc>&x )

函数将x合并到*this身上,两个lists的内容都必须先经过递增排序。

参数list的内容会清空,合并过程有排序!!!



下面看一下整个代码的具体实现。

代码开头先进行了一下校验。

然后声明了两个变量,carry和counter[64]都是拿来作为中间变量进行中转的。

counter[0]存放2^1次方个元素

counter[1]存放2^2次方个元素

依次类推


怎样存放呢,原则是当第i个counter[i]中存放的内容个数等于2^(i+1)时,就把counter[i]里的内容转移到counter[i+1]

假设我们有个list:7,9,8,6,11。

第一轮:

开始时:

carry:NULL

fill:0

counter[0]:NULL

counter[1]:NULL

1.carry.splice取出第一个元素

carry=7


2.现在i==fill跳过while循环

3.carry.swap之后,carry和counter[0]交换

carry:NULL

counter[0]:7

counter[1]:NULL


4.现在执行if(i==fill) ++fill;

fill=1;


结束时:

carry:NULL

fill:1

counter[0]:7

counter[1]:NULL

第二轮:

1.carry.splice取出第二个元素

carry=9


2.现在i<fill且counter[0]非空,执行while循序内部内容

couter[i].merge[carry]

carry:NULL

counter[0]:7,9

counter[1]:NULL

注意这里是的放置已经经过了排序,在merge里实现

carry.swap[counter[i++]

carry:7,9

counter[0]:NULL

counter[1]:NULL




3.i=1,fill=1退出while循环

4.carry.swap之后,carry和counter[1]交换

carry:NULL

counter[0]:NULL

counter[1]:7,9




5.现在执行if(i==fill) ++fill;

fill=2;
结束时:

carry:NULL

fill:2

counter[0]:NULL

counter[1]:7,9



这样就把两个元素归并到了counter[1]中,下面不再繁琐的分析

取出第三个数字8,放到counter[0]中,现在counter[0],counter[1]中的数字个数都小于规定数字:

counter[0]:8


counter[1]:7,9


取出第四个数字6,放到counter[1]中,这是counter[0]中个数定为2,需要转移到counter[1]中:

counter[0]:NULL


counter[1]:6,7,8,9


这时候counter[1]的个数等于4了,需要把所有的数字转移到counter[2]中

counter[0]:NULL


counter[1]:NULL


counter[2]:6,7,8,9


然后取出11放到counter[0]中,链表所有元素取完了。结束while循环。

把所有结果归并。

这里fill其实表示了一个2^(i+1)次方的判定!!

整个过程总结如下:

将前两个元素归并,再将后两个元素归并,归并这两个小子序列成为4个元素的有序子序列;重复这一过程,得到8个元素的有序子序列,16个的,32个的。。。,直到全部处理完。主要调用了swap和merge函数,而这些又依赖于内部实现的transfer函数(其时间代价为O(1))。该mergesort算法时间代价亦为n*lg(n),计算起来比较复杂。list_sort中预留了 64个temp_list,所以最多可以处理2^64-1个元素的序列,这应该足够了。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐