[4.3]STL容器List之内部Sort算法原理

程序员文章站 2022-06-04 17:21:02

...

引言：

list没有使用STL的通用Sort算法，而是实现了自己的内部排序算法,下面是算法源代码，这个短小的源代码Confuse很多人：

/// <summary>
		/// default sort algorithm in stl  ()
		/// </summary>
		void sort_4list_sgi_stl_version()
		{
			if (count < 2) return;
			List<T> carry;
			List<T> counterX[64];
			int fill = 0;         // counterX下标控制变量 
			while (!IsEmpty()) 
			{
				carry.splice(carry.begin(), begin(),*this);
				int i = 0;        // 临时的counterX下标控制变量，确定i不会超过64吗？

				                  // 下面这个while循环是将counterX[i]及其之后的非空集合合并到carry
				while(i < fill && !counterX[i].IsEmpty()) 
				{
					counterX[i].merge(carry);   // 将carrry合并到counterX[i],counterX[i]为有序序列
					carry.swap(counterX[i++]);  // counterX[i]与carry交换
				}
				carry.swap(counterX[i]);        // counterX[i]缓存当最新的计算结果
				if (i == fill)                  //表明只有当前的counterX[i]存在数据,fill后移
				{
					++fill;
				}
			} 
			// 将counterX[fill-1]之前的所有数据merge,即可获得最终已排好序数据
			for (int i = 1; i < fill; ++i)
			{
				counterX[i].merge(counterX[i-1]);
			}
			this->swap(counterX[fill-1]);
		}

算法设计原理：

1、这个算法使很多人Confused。下面是我的改进，如果这个Sort写成下面这样，相信很多人不会再Confuse.

2、这个化版本应该是设计STL Sort内部算法的原始设计版本。

3、我在想STL的设计者Alexander Stepanov为什么要改变这个内部Sort的实现方式，难道就像P.J.Plauger实现的版本一样，就是为了让你看不懂，又如何？

(SGI的版本在可读性方面还是值得尊敬的)

/// <summary>
		/// Variant version of merge sort
		/// 1. splice the first node to carry
		/// 2. merge carry to result (result is a ordered sequence)
		/// 3. goto step 1 until count==0
		/// 4. swap result & this
		/// </summary>
		void sort2gyue()
		{
			if (count < 2) return;
			List<T> carry;	// tmp
			List<T> result; // tmp result sequence sorted
			while (!IsEmpty()) 
			{
				carry.splice(carry.begin(), begin(),*this); // get the first node to splice to carry
				result.merge(carry);                        // merge to result (result is ordered sequence)
			}
			swap(result);									// swap ordered sequence with this
		}

sort2gyue

算法流程：

1、原始待排序的链表L1，定义临时链表carry与缓存结果的链表result

2、取L1的begin处的节点splice到carry

3、将carry数据merge到result,此时result为一个有序集

4、算法回到2.当L1的节点数为0时，循环结束。result为完成排序的集合

5、将result与L1交换，此时，完成L1的排序（L1的headAddr变了，其它节点Addr未变）

图解下面的①-③

①原始数据

[4.3]STL容器List之内部Sort算法原理

②取begin处节点splice到carry

[4.3]STL容器List之内部Sort算法原理

③carry数据merge到result,result的结果为一个有序集，重复取p2,p3........pn，最终得到的结果为一个有序集

[4.3]STL容器List之内部Sort算法原理

原始算法分析

我查看了SGI STL与源于SGI版本的STLPort 5.2.1的内部实现，使用是同一个算法，算法结构一点都没改动，只时变量命名换了

1) 现在再回过头来看list提供的默认排序算法，这个算法真是有点把简单问题实现复杂化了。

2) 实际上提供一个carry与一个counter[1]缓存就够了，不必要提供64个counter数据。

3) 这个counter[64]的功能主是是用于缓存从carry链表merge过来的数据。

4)同时为counter设计了一个上限游标fill，最终循环结束，目标排序的list数据全部转移到counter[0]-counter[fill-1]中来了，merge这部分counter数据到counter[fill-1]，获得最终的排序数据，最终将counter[fiil-1]与this交换，即可完成排序。

附：提供带比较器的版本

[4.3]STL容器List之内部Sort算法原理