SGI-STL源码剖析之list::sort()


// list 不能使用STL 算法 sort(),必须使用自己的 sort() member //function,因为STL算法sort() 只接受RamdonAccessIterator.
// 本函式采用 quick sort.

template <class T, class Alloc>
void list<T, Alloc>::sort() {
  // 以下判断,如果是空白串行,或仅有一个元素,就不做任何动作。
  // 使用 size() == 0 || size() == 1 来判断,虽然也可以,但是比较慢。
  if (node->next == node || link_type(node->next)->next == node) return;
  // 一些新的 lists,做为中介数据存放区
  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 = 1; i < fill; ++i)
     counter[i].merge(counter[i-1]);

  swap(counter[fill-1]);
}

性质:
counter[i]的元素个数只可能有三种可能:0,2^(i-1),2^i
其中2^i为counter[i]的不稳定状态,只要满足该元素个数,在该次循环中最终交换到i+1中。若此时i+1中的元素个数为2^(i+1),则持续向上交换到i+2中。carry作为且仅仅作为此交换的中转。

Quick Sort 还是 Merge Sort?

首先,看一下两个算法的思想:

  • 快速排序,采用分而治之的思想,是Hoare提出的一种划分交换排序,非stable sort,属于Exchange sorts的范畴
  • 归并排序,采用分而治之的思想,是Neumann提出的一种基于比较的排序,绝大数实现为stable sort,属于Merge sorts的范畴。

(可参考维基百科中两种算法的描述)
经过调试可知,list sort算法属于merge sort。测试可得到同样的结论,以下是测试代码:

#include<iostream>
#include <list>
using namespace std;
#include <stdlib.h>
#define TESTNUM 500
struct Point
{
	int value;
	int num;
	friend bool operator <(Point v1,Point v2)
	{
		return v1.value<v2.value;
	}
};
int main()
{
	freopen("STL List Test.txt","w",stdout);
	list<Point> container;
	srand(0);
	for (int i=0;i<TESTNUM;i++)
	{
		Point p;
		p.value=rand()%100;
		p.num=i;
		container.push_back(p);
	}
	container.sort();
	for (list<Point>::iterator it = container.begin(); it != container.end(); ++it)
	{
		printf("%d   %d\n",(*it).value,(*it).num);
	}
}
# STL