Partial and Total Orders

strict weak ordering导致公司级故障 - 高性能架构探索 - 博客园

std::sort - cppreference.com  std::less - cppreference.com

cppreference.com不说人话，只好先看:

Partial and Total Orders - Eli Bendersky's website (thegreenplace.net)

搜一下C++写的quicksort，别用STL的sort得了。C里一直有qsort，缺点: 1. 只能传函数指针，不能inline; 2. 极端情况下堆栈深？

发泄下: Given a set A, a relation on A is a set of pairs with elements taken from A. {1, 1, 2, 3}是集合吗？集合里不能有重复元素啊。[1, 1, 2, 3]不能排序吗？窃以为std:sort用relation和order来描述comparator是狐假虎威。文档应该这么写: 比较器比较a和b的大小。return a<b导致正序排列，return a>b导致逆序排列，不要用return a<=b; 或 return a>=b; 因为它们在a=b时返回true。而我们在partition时，为了提高那么一丢丢性能，没有判断数组是否会越界，即我们不是while (i < N && cmp(ary[i], x)); 而是while(cmp(ary[i], x)). 我们觉得把这个改掉不如用晦涩的文档把你们整晕。要是阿猫阿狗都能写个C++程序而居然不core dump，那我们的niubility何在？我们还要cout << an_obj;就报出五颜六色的250行错误信息。从N往0时越界更好玩: vector在堆里分配，但std:sort可以对局部变量int ary[1000];排序，理论上可以破坏函数的返回地址和调用者们的堆栈框架吧？

There are a number of useful properties relations could have. Here are just a few:
1. Reflexive: 每个元素都和它自己有关系
2. Irreflexive: 集合里的任意元素都和它自己没关系。1个元素和它自己有关系，2个元素和它自己没关系，既没有Reflexive属性，也没有Irreflexive属性。
3. Transitive: x R y 且 y R z 推出 x R z. 关系也是个集合，换句话说：如果R具有Transitive这个属性，且xRy和yRz都属于集合R，那么xRz也属于集合R.
4. Symmetric: 如果R具有Symmetric这个属性，且xRy属于集合R，那么yRx也属于集合R.
5. Antisymmetric: 如果R具有Antisymmetric这个属性，且xRy属于集合R，那么yRx不属于集合R. 与Reflexive和Irreflexive类似，某个R可能既不Symmetric也不Antisymmetric。

There are two kinds of partial orders we can define - weak and strong. The weak partial order is the more common one.

A weak partial order (also known as non-strict) is a relation on a set A that is reflexive, transitive and antisymmetric. <=是个例子。

A strong partial order (a.k.a. strict) is a relation on a set A that is irreflexive, transitive and antisymmetric. <是个例子。irreflexive说的是3 < 3不成立。

A total order is a partial order that has one additional property - any two elements in the set should be related. Total order requires us to be able to order all elements in a set.