algorithm - 对给定的成对排序进行排序

Question

我有n变量 ( Var 1 ... Var n ) 并且不知道它们的确切值。 n choose 2这些 n 之间的成对排序变量已知。例如，已知 Var 5 <= Var 9 , Var 9 <= Var 10等等所有对。此外，还已知这些成对排序是一致的并且不会导致始终相等的退化情况。也就是说，在上面的例子中，不等式Var 10 <= Var 5不会出现。

对于此类问题，对所有变量进行排序的最有效排序算法是什么？

Answer 1

成对排序是任何(基于比较的)排序唯一需要的东西，因此您的问题归结为“什么是最有效的基于比较的排序算法”。

为了回答这个问题，我建议您查看 Quicksort , Heapsort , Timsort , 可能 Mergesort并看看在内存要求、编程复杂性等方面什么最适合您的情况。
我发现 Quicksort 是实现一次性程序最快的方法。