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);
	}
}

本文作者 ： cyningsun
本文地址 ： https://www.cyningsun.com/04-08-2011/stl-list-sort.html
版权声明 ：本博客所有文章除特别声明外，均采用 CC BY-NC-ND 3.0 CN 许可协议。转载请注明出处！