假设我有一个元组列表：
[(a1, b1), (a2, b2), ..., (an, bn)]
我可以按a或b对它们进行排序，但不能同时对两者进行排序。
但是如果我想同时对它们进行排序怎么办？衡量其排序效果的好方法是顺序错误的“ a”值对的数量，以及顺序错误的“ b”值对的数量。什么算法可以快速执行此操作？
最小化不同损失函数的算法也很有趣，但我认为对我的应用程序最好的是最小化不一致对。
只需将a组件用作抢七游戏，就可以按b组件对列表进行排序。 （反之亦然。）或者，如果它们是数字，则可以按两个成分的总和a + b进行排序。可以使用任何有效的基于比较的排序算法在O（n log n）时间内完成此操作。
此解决方案有效，因为对于每对元素，损耗函数可以写为单个损耗函数的总和。对于诸如(2, 4)与(3, 3)之类的货币对，无论它们的相对顺序如何，其对的损失都是1。类似地，当两对货币对相等时，例如(4, 5)与(4, 5)，则无论相对顺序如何，该对的个人损失均为0。
唯一的非恒定个体损失函数适用于其中一个分量较大而另一个分量较大或相等的对，例如(2, 4)与(3, 4)，或(2, 4)与(3, 5)。上述每个排序顺序会将所有此类对以彼此相对的最佳顺序放置。这同时使损失函数中的每一项最小化，因此使总损失最小化。
请注意，此<>。对于三元组或更高的元组，像这样简单的解决方案将行不通，但我的原始答案中的想法可以进行调整（请参见下文）。但是，调整它们并不容易，因为该图不一定是非循环的。
原始答案（扩展）
(a_i, b_i)是图中的一个节点。除非i → j和a_i <= a_j都相等，否则请插入有向边b_i <= b_j。对于a_i < a_j和b_i > b_j的任何对，反之亦然，以及a_i = a_j和b_i = b_j的任何对，都没有边。边缘的存在等效于节点i和节点j的相对顺序之间的优先级；如果没有边缘，那么无论这两个节点的相对顺序如何，损失都是相同的。
对于2元组的情况，从构造该图的角度来看，很容易看出该图是非循环的。因此，topological sorting algorithm将找到一个排序，以使所有边都指向“正向”，即只要有边i，节点j就会出现在节点i → j之前。该排序明显地使损耗函数最小化，因为它同时使每对i，j的单个损耗最小化。
结果顺序中唯一不和谐的对就是那些必然不和谐的对；那些，无论该对以哪种方式结束，要么a组件乱序，要么是b组件。
实际上实现拓扑排序算法不需要显式构造图；您可以将“节点”和“边缘”视为implicit graph，使用比较来查找边缘，而不是在某种图形数据结构中查找它们。为了避免在每次迭代时扫描整个列表以查找节点的邻居，您可以利用以下优势：边关系为transitive：如果节点A仅具有节点B，C和D的边，则节点B只能具有C和D的边缘。在最坏的情况下，这将花费O（n²）时间，但应比蛮力有效。