如何在C++中编写一个通用的排序函数？
是否有任何可能的方法在C++中使用单一函数对自然意义上的所有类型的数据进行排序？在我的情况下，我定义了一个基于模板数据类型的链表结构，并且我想将它包含的数据作为链表排序。如何在C++中编写一个通用的排序函数？
是的，你可以很自然地用链表实现插入排序。您可以使用与std::sort类似的界面编写模板化功能。
然后，您可以使用operator<来比较任何类型的元素或Compare函数。
您可以允许您的列表作为输入，并返回一个排序列表作为输出。
复杂性会下降到O(n^2)与插入排序，但这是IMO最简单的方法。 我不认为你可以做更好的随机存取容器。也许合并排序可以实现列表。看起来像一个很好的候选人。
或者，您可以将列表复制/移动到支持随机访问迭代器的结构中，并用std::sort对它进行排序并将其转换回列表。这在技术上具有更好的复杂性，但是由于2次变换操作而具有相当大的常数因子。但对于大名单，最终会更快。
你真的不应该在意拷贝或移动，而是'交换'。这也是'std :: sort'的作用。 – pmr
当你计算纯粹的计算复杂性时，当然是。当你使用数据结构对小集进行排序时（我知道你可以说我不应该关心小数据集，因为它们的定义很快），但值得记住的是复制东西也需要时间。而“交换”无论如何都是副本或移动，不是吗？此外，我认为在一个设计不好的算法中（有点像我这里粗略的草图），你将受到记忆的束缚，交换次数可能变得不那么占优势。我看到一些假设'malloc'很好的例子，并且打破了它们的复杂性。 – luk32
我并没有试图说复制或移动对性能无关紧要，而是交换概括了复制构建/移动构建。如果你有一个很好的定义（在数学意义上）“交换”，你的低层算法不需要关心底层机制。 – pmr
有多种尺寸，你可以通过通用的意思是：
- 通用相对于数据
- 通用相对于容器
第一种是最简单的解决。我们需要考虑排序需要什么工作：我们的数据为strict weak ordering。现在我们知道我们需要提供给排序算法的函数的性质，并需要一种方法来传递函数。在C++中，假设operator<实现这样的顺序或将函子传递给实现它的算法已成为常态。所以签名会变成：
template<typename T, typename Comp = std::less<T>>
my_sort(my_list<T>& l, Comp c = Comp());
我们的排序算法必须执行另一个操作：交换元素。正如我们在这个我们自己的小世界中，我们可以假设我们所有的类型都有一个成员函数T::swap(T& rhs)，它正是这样做的。在现实世界中，我们将使用免费函数std::swap（具有非限定的调用和使用指令，但这是一个晦涩的技术性）。
第二个问题更棘手，你实际上不想解决它，因为你只希望你的排序算法在你的列表实现上工作。我鼓励您深入探讨std::sort及其要求，了解为什么它以这种方式实施，以及为什么它不适用于std::list。
请注意，对于列表，最好修复内部列表指针而不交换数据（可能不可交换）。 – Jarod42
Ahem ['std :: sort']（http://en.cppreference.com/w/cpp/algorithm/sort）？ – Borgleader
@Borgleader - 海报说他有一个链表，它不会与'std :: sort'一起工作，因为它不太可能是一个随机访问结构。 – Sean
@肖恩你错过了这一点。问题是“是否可能”。是的，看看std :: sort。 – Borgleader