我想到的是一个 SortedIterator，它接受一个 Less 函数，该函数将用于使用所有已知算法对容器进行排序。
暴力实现当然会保留原始元素的副本，或者保留对原始列表中元素的引用/指针。
是否有一种高效方法可以按明确定义的顺序进行迭代，而无需实际对列表进行排序？我问这个问题是出于对算法的好奇心，我希望答案是否定的(或者是，但有一个很大的但是)。它是出于 C++ 风格的思维方式提出的，但实际上是一个非常普遍的与语言无关的前提。
最佳答案
如果您想要 O(1) 内存，则 O(n^2) 复杂度是我们所知的唯一方法。否则我们可以用同样的方式改进选择排序算法。任何其他排序机制都依赖于能够重构部分数组(合并排序依赖于对数组的部分进行排序，qsort 依赖于基于主元拆分数组等等)。
现在，如果您放松内存限制，您可以做一些更高效的事情。例如，您可以存储一个堆来包含最小值 x 元素。因此，经过一次 O(Nlog x) 迭代后，您将获得迭代器的 x 个元素。对于下一次传递，仅限制大于迄今为止发出的最后一个元素的元素。您需要进行 N/x 遍才能获得全部。如果 x ==1 则解为 O(N^2)。如果 x == N，则解为 O(Nlog N)(但常数比典型的 qsort 更大)。如果数据在磁盘上，那么我会将 x 设置为尽可能多的内存，减去几 MB 以便能够读取驱动器的大块。
关于algorithm - 是否有一种有效的方法可以按特定顺序迭代未排序的容器，而无需排序/复制/引用原始容器？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50230319/