// 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 许可协议。转载请注明出处！
