Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 数据结构, 算法 » , ,

STL中链表的排序

STL中的链表使用起来非常方便,但其不能使用标准的排序函数sort,那么怎么对其进行排序呢?其实list自带有sort成员函数,使用的是非递归的归并排序,本文将讲解其排序的基本思想及具体代码实现。

list排序

list中存储的数据在内存中不一定是连续的,其通过next指针进行相连,故list的迭代器不是一个随机访问迭代器,不能输入到algorithm头文件中的sort函数中进行排序,但是可以通过list自带的成员函数sort进行排序。

list自带的sort排序使用的是归并排序,为什么不使用快速排序呢?尽管链表也可以使用快速排序,但这并不是链表排序的最优算法,归并排序才最适合链表的排序,因为普通数组归并时需要O(n)的额外空间,而链表归并时可以通过修改指针直接进行,可以直接O(1)空间搞定。另外,普通的归并排序需要先找到中间节点把链表分成两部分,这个找中间节点的操作非常耗时,STL中使用的是直接两两归并的方法,具体见以下介绍。

下面先用一个简单的例子说明如何使用list进行排序,其实现的功能是把二维坐标上的点按x轴排序,如果x坐标相等,则按y轴排序。

#include <list>
#include <cstdio>
#include <algorithm>
using namespace std;

struct Node //坐标节点
{
	int x, y;
	Node (int xx = 0, int yy = 0) : x(xx), y(yy) {}
};

struct cmp //仿函数
{
	bool operator()(const Node &a, const Node &b)
	{
		//x坐标升序,x相同则按y坐标升序
		return a.x < b.x || (a.x == b.x && a.y < b.y);
	}
};

int main()
{
	Node a1(1, 1), a2(1, 0), a3(0, 1), a4(0, 0); //待排序4个点
	list<Node> l;
	l.push_back(a1);
	l.push_back(a2);
	l.push_back(a3);
	l.push_back(a4);
	//sort(l.begin(), l.end(), cmp()); 编译错误
	l.sort(cmp());
	for (list<Node>::iterator p = l.begin(); p != l.end(); ++p)
		printf("%d %d\n", p->x, p->y);
	/* 程序输出**
	0 0
	0 1
	1 0
	1 1
	************/
}

排序算法

上面说到,STL的归并排序并不是普通的把一个大链表分成两个小链表分别进行递归排序,然后再归并结果的方法,而是一个两两归并的方法。

例如,对以下数组排序:8 7 6 5 4 3 2 1,具体的步骤为:

  1. 本身就是长度为1的两两归并的结果:8 7 6 5 4 3 2 1
  2. 以长度为2的大小进行两两归并:7 8 5 6 3 4 1 2
  3. 以长度为4的大小进行两两归并:5 6 7 8 1 2 3 4
  4. 以长度为8的大小进行两两归并:1 2 3 4 5 6 7 8
  5. 全部元素排序完毕。

STL中实现的思想跟上述思想一致,但具体实现的顺序跟上面所述又有所不同。下面先看代码中的实现。

注意,STL的实现版本非常多。

  • HP STL是是第一个STL的实现版本,是其它STL实现的根源。它是STL之父Alexander Stepanov在惠普的Palo Alto实验室工作时,和Meng Lee共同完成的,但现在直接使用的较少。
  • Visual Studio中使用的是P. J. Plauger版本的STL,由P. J. Plauger本人实现,是HP STL的一个继承版本。但该源码可读性比较差,这里不仔细讨论。
  • Linux下GCC使用的是SGI版本的STL,是由Silicon Graphics Computer System, Inc公司实现的,也是HP STL的一个继承版本,其源码可读性较好。

本文将使用SGI STL v3.3进行介绍,具体的SGI STL源代码可以从SGI 官网 进行下载。

//根据__comp比较规则对本链表排序
template <class _Tp, class _Alloc>
template <class _StrictWeakOrdering>
void list<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp)
{
	//元素个数为0(即next为自己)或为1(即next的next为自己)时不需排序
	if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node)
	{
		list<_Tp, _Alloc> __carry;      //临时链表
		list<_Tp, _Alloc> __counter[64];//存放长度为2^i的链表的排序结果
		int __fill = 0;                 //当前最多元素个数为2^fill个
		while (!empty())
		{
			//每次从原链表中取出一个元素
			__carry.splice(__carry.begin(), *this, begin());

			int __i = 0;
			//把carry中的新元素与counter中的结果逐个归并
			while(__i < __fill && !__counter[__i].empty())
			{
				__counter[__i].merge(__carry, __comp);
				__carry.swap(__counter[__i++]);
			}
			//把归并后的结果存放到counter中第i个位置
			__carry.swap(__counter[__i]);

			//已经达到2^fill个元素,fill自增
			if (__i == __fill) ++__fill;
		} 

		//把所有已排序的结果进行最后归并
		for (int __i = 1; __i < __fill; ++__i) 
			__counter[__i].merge(__counter[__i-1], __comp);

		//把排序完毕的结果存回到原来的链表中
		swap(__counter[__fill-1]);
	}
}

根据以上算法,我们有若干个临时链表counter[i],每个保存的是长度为2^i的链表的排序结果。对于每次循环,从原链表中取出一个元素,逐个跟counter[i]的链表归并,并保存到最后的counter[i]中。

下面对于原来的例子的具体执行过程。

  1. 原链表为8 7 6 5 4 3 2 1。fill = 0。
  2. 取出8,把8放到counter[0]中。fill = 1。
  3. 取出7,把7跟counter[0]的8归并,得到7 8;把7 8放到counter[1]中。fill = 2。
  4. 取出6,把6放到counter[0]中。
  5. 取出5,把5跟counter[0]的6归并,得到5 6;把5 6跟counter[1]中的7 8归并,得到5 6 7 8,放到counter[2]中。fill = 3。
  6. 取出4,把4放到counter[0]中。
  7. 取出3,把3跟counter[0]的4归并,得到3 4;把3 4放到counter[1]中。
  8. 取出2,把2放到counter[0]中。
  9. 取出1,把1跟counter[0]的2归并,得到1 2;把1 2跟counter[1]中的3 4归并,得到1 2 3 4;把1 2 3 4跟counter[2]的5 6 7 8归并,得到1 2 3 4 5 6 7 8;把1 2 3 4 5 6 7 8放到counter[3]中。fill = 4。
  10. 原链表为空,退出循环。
  11. 把counter中的所有元素归并(处理长度不是2的幂次的情况),把最终结果保存到原链表中。

以上就是整个算法的基本思想。其中还涉及到一些list内部的函数,这里一并讲解。

首先是swap函数,可以在O(1)时间内交换两个链表。

//交换本链表与链表__x
void swap(list<_Tp, _Alloc>& __x)
{
	//交换链表中的指针
	__STD::swap(_M_node, __x._M_node);
}

然后是merge函数,可以归并两个已排序的链表。就是使用一般的归并思想,两个链表均从头到尾进行扫描。

//归并已排序的本链表和链表__x,根据比较规则__comp
template <class _Tp, class _Alloc>
template <class _StrictWeakOrdering>
void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x, _StrictWeakOrdering __comp)
{
	iterator __first1 = begin();
	iterator __last1 = end();
	iterator __first2 = __x.begin();
	iterator __last2 = __x.end();
	while (__first1 != __last1 && __first2 != __last2)
		if (__comp(*__first2, *__first1))
		{
			//链表2中的元素较小,将其插入到链表1中
			iterator __next = __first2;
			transfer(__first1, __first2, ++__next);
			__first2 = __next;
		}
		else
			//链表1中的元素较小,无须额外的插入动作
			++__first1;

	//链表2非空,将其全部插入到链表1中
	if (__first2 != __last2) transfer(__last1, __first2, __last2);
}

merge函数中使用到了辅助函数transfer函数,实现链表的移动,主要涉及到一些链表指针的修改,具体细节较为繁琐,这里不详细展开。

//把[__frist,__last)的内容迁移到本链表中__position位置上
void transfer(iterator __position, iterator __first, iterator __last)
{
	if (__position != __last) //本来的位置正确时无须额外操作
	{
		// Remove [first, last) from its old position.
		__last._M_node->_M_prev->_M_next     = __position._M_node;
		__first._M_node->_M_prev->_M_next    = __last._M_node;
		__position._M_node->_M_prev->_M_next = __first._M_node; 

		// Splice [first, last) into its new position.
		_List_node_base* __tmp      = __position._M_node->_M_prev;
		__position._M_node->_M_prev = __last._M_node->_M_prev;
		__last._M_node->_M_prev     = __first._M_node->_M_prev; 
		__first._M_node->_M_prev    = __tmp;
	}
}

最后,我们再列出Visual Studio使用的PJ版本STL的list sort算法的实现,仅供比较。

template<class _Pr2>
void sort(_Pr2 _Pred)
{	// order sequence, using _Pred
	if (2 <= this->_Mysize)
	{	// worth sorting, do it
		const size_t _MAXBINS = 25;
		_Myt _Templist(this->_Getal()), _Binlist[_MAXBINS + 1];
		size_t _Maxbin = 0;

		while (!empty())
		{	// sort another element, using bins
			_Templist._Splice_same(_Templist.begin(), *this, begin(), ++begin(), 1);

			size_t _Bin;
			for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin].empty(); ++_Bin)
			{	// merge into ever larger bins
				_Binlist[_Bin].merge(_Templist, _Pred);
				_Binlist[_Bin].swap(_Templist);
			}

			if (_Bin == _MAXBINS)
				_Binlist[_Bin - 1].merge(_Templist, _Pred);
			else
			{	// spill to new bin, while they last
				_Binlist[_Bin].swap(_Templist);
				if (_Bin == _Maxbin)
					++_Maxbin;
			}
		}

		for (size_t _Bin = 1; _Bin < _Maxbin; ++_Bin)
			_Binlist[_Bin].merge(_Binlist[_Bin - 1], _Pred);	// merge up

		_Analysis_assume_(0 < _Maxbin);

		splice(begin(), _Binlist[_Maxbin - 1]);	// result in last bin
	}
}
上一篇: 下一篇:
  1. 最好说明下,merge的操作,会将__carry 合并进 __counter[__i],__carry置空。
    看这里的时候 不太好懂,还得往下看transfer才能明白

  2. ▇▇▇▇无毒爽站【htTP://v.ht/aS8H】 ,在线爽,夫妇必备 ▇▇▇▇▇

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论