简短版本：
我正在寻找一种技术，尽管值略有变化，但随着时间的推移，将近排序的数据保持接近排序的顺序。
场景如下：
在 3D 图形领域，在绘制之前从前到后对对象进行排序通常是有益的。 随着场景的变化或场景视图的变化，这些数据可能需要重新排序，但它通常非常接近排序顺序（即帧之间不会有太大变化）。 数据完全按排序顺序排列也不重要。 最糟糕的事情是多边形将被渲染，然后完全隐藏。 这是一个小小的性能打击，但不是世界末日。
考虑到这一点，是否可以提前对数据进行一次排序，然后每帧对数据应用一次最小的补丁，以确保数据大部分保持排序？ 在这种情况下，如果大多数对象按升序排列，则数据将被视为大部分已排序。 也就是说，距离其正确位置 10 步的 1 个对象比距离其正确位置 1 步的 10 个对象要好得多（好 10 倍）。
还值得注意的是，数据可以继续半定期修补，因为数据通常每秒呈现 30 次（左右）。 只要计算有效，就可以随着时间的推移继续完成，直到更改停止并且列表完全排序。
现有理念：
我对这个问题的下意识反应是：
- 在
加载数据时对数据应用
n log n排序，并在发生大量更改时（我可以轻松跟踪）。
当数据开始缓慢变化时（例如，当场景旋转时），对数据应用某种（线性）传递以交换向后邻居并尝试保持排序顺序（我认为这基本上是 shell 排序 - 也许有更好的算法用于此单次传递）。
继续对每一帧进行一次部分排序，直到更改停止并且数据完全排序
返回到步骤 2 并等待更多更改。
如果输入大部分是排序的，则在 O（n） 时间内运行多种排序，如果数据未排序，则在 O（n log n） 时间内运行。 听起来你可以很容易地使用它。 Timsort就是这样一种类型，我相信，现在是python和java的默认排序。 平滑排序是另一个相当容易实现的。
从您的描述来看，听起来排序顺序会发生变化，而无需更改数据本身。 例如，您更改了相机，因此即使您没有修改任何多边形，排序顺序也应该更改。
如果是这样，则无法在排序顺序更改发生时直接检测它们。如果可以的话，我会为多边形列表创建桶，并在触摸该桶中的"足够"多边形时创建度假村桶。
但我敢打赌你的系统不会那样工作。排序由视口确定。在这种情况下，排序前面的多边形比末尾的多边形重要得多。
所以我会把多边形列表分成五分之一或类似的东西。从前到后，因此前五分之一是最靠近相机的部分。我会在每一帧中对第一段进行完全排序。我会将第二段划分为子段 - 再次说 5 个 - 并在每一帧对每个子段进行排序，这样每 5 帧第二个五分之一被完全排序。将第三段到第五段分成 15 个子段，每 5 帧执行一次，以便其余部分每 75 帧完全排序一次。在 60 fps 下，您将每秒完全重新显示列表一次以上。
优先考虑列表前面的好处是1. 前面的多边形在屏幕上往往会更大，并且更频繁地无法通过深度测试。列表末尾的错误订单通常无关紧要。2.由于相机变化，列表的前面更容易发生排序变化。
此外，还选择了那些略有重叠的线段范围，以便多边形可以以 2 种方式迁移到其正确的线段。
@OP：再考虑一下。您可能更关心的是排序成本保持有限 - 而不是随着场景复杂性而爆炸式增长。特别是因为一个非常复杂的场景应该 - 令人惊讶 - 不太容易受到不良排序的影响（因为通常多边形变小）。
您可以定义每个帧愿意执行的固定排序量。使用预算的 50% 用于您能负担得起的尽可能多的列表前面，将预算的 25% 用于对下一个区域进行排序，将 25% 用于其余区域。
假设您预算每帧排序 1000 个多边形，并且场景中有 10000 个多边形。每帧对前 500 个多边形进行排序。为下一个区域每十帧对 250 个多边形进行排序。所以帧 501 上的 750-1-1，帧 751-1000 上的 2 等。然后将列表的其余部分划分为 250 个帧段，并根据您需要的帧数对它们进行循环排序。
这使得排序成本保持不变，因为场景变得越来越复杂，并且很容易调整，您只需将排序预算调整到您可以承受的程度即可。
我将在这里提出一个借鉴其他解决方案的解决方案。当然，我们从初始化时的完整对象开始。
我会做的是始终对每帧的对象执行 10 次线性时间运行（如果您发现您的对象已经完全排序，则提前终止）。例如，每次运行可以是一次气泡排序，在整个数组上具有 shell 排序样式的间隙：对于从 0 到 n-gap-1 的所有 i，比较 A[i] 和 A[i+gap]，如果未排序，则交换它们。您可以使用固定的间隙序列，或者更好的是，让它在帧之间变化;无论哪种方式，如果您执行足够多的对象不会更改的帧，您将拥有一个完全排序的序列。您甚至可以混合不同类型的子算法来运行，只要每次迭代都能提高"排序性"。
您可以添加拉斐尔·巴普蒂斯塔（Rafael Baptista）的想法，即通过在前段进行一次额外的运行来轻松确定场景前部的优先级，或者选择将前半部分的差距除以二，或类似的东西。
它不像你想象的问题那样整齐，因为你所要做的就是将相机旋转90度，而排序的基础是完全不同的轴。（例如，X 轴和 Y 轴是独立的 -- 向下看 X 轴将导致排序顺序不依赖于 X 轴，向下看 Y 轴将导致排序顺序不依赖于 Y 轴。即使是 5 度的转弯也会导致远处的"近"（就 Z 阶而言）的东西突然变得"远"。
老实说，为对象生成绘制调用通常比对它们进行排序花费更多的时间，特别是如果你的场景具有优化的排序算法，并且你的游戏具有现代视觉复杂性。
排序实际上可以是 O（n），特别是使用基于直方图的算法或基数样式的算法。（是的，基数排序适用于整数，所以你必须将你的世界坐标缩放到整数，但通常情况下，除非你有一个巨大的世界，否则这已经绰绰有余了。
话虽如此，由于您已经在对正在绘制的所有内容进行O（n）操作，因此按帧重新排序不会是一个大问题，尤其是在高级和低级优化的情况下。
解决此问题的另一种常见方法是使用场景图，但出于您的目的，它最终基本上是每帧的重新排序。但是，您可以将视锥剔除、阴影剔除和细节层次计算构建到场景图遍历中。
如果您正在寻找近似值，则不要执行 z 距离排序，而是执行真实距离排序，并更频繁地更新靠近对象的排序顺序，而对其他对象（取决于相机行进的距离）的频率更低。这可以工作，因为如果您离对象更远，移动不会导致查看器的角度经常更改，这反过来意味着旧的排序数据更有可能有效。我不喜欢这个，因为我喜欢算法，它允许我的游戏在地图上传送而不会出现任何问题。（请注意，从磁盘流式传输资产成为传送的真正问题。
Shell 排序适用于唯一值很少的列表和一些"需要短代码且不使用调用堆栈"的方案。
在您的情况下，您需要一种称为自适应排序的东西，这意味着算法"利用其输入中的现有顺序"。
如果您的空间很紧，您可以只使用自适应且就地的直接插入排序。
否则，您可以按照@RunningWild建议尝试 Timsort 和 Smoothsort，它们都是自适应排序算法。