java - 顺序很少变化的快速排序

Question

我正在开发一款具有 ScrollView 的 2D 游戏(想想红色警戒或塞尔达传说)，但我在绘图方面遇到困难。

基本上有两种类型的对象绘制在 map 上。有些位置固定(如树木和建筑物)，有些位置移动(玩家、敌人、飞箭)。

为了让事物以正确的方式出现在彼此面前，它们需要以特定的顺序绘制(首先是远处的物体，然后朝向“相机”)。

现在，每次游戏更新(每秒 100 次)时，我都会对所有对象(两种类型)的列表进行排序，这感觉就像是对 CPU 时间的巨大浪费。对象的顺序很少发生变化，即使发生变化，它们通常也只会在列表中向上或向下移动一个位置。

另一个问题是只需要考虑实际在屏幕上的对象。由于包含 1000 个对象的 map 可能会变得非常大，我不想每秒对它们进行 100 次排序。

您建议我如何解决这个问题？

Answer 1

Bubble Sort最好的情况是元素已经排序。在那种情况下你会得到 O(n) 比较。根据维基百科:

In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).

但由于链接文章中提到的各种原因，它被认为是一个“糟糕”的算法。您可能想要剖析它与插入排序(对于排序列表也是 O(n))之间的区别，看看哪个在实践中更快。

另一种选择是使用一种数据结构，将已排序的项目保存在其中，并在项目的位置发生变化时得到通知。如果对象与重新绘制的频率相比移动不多，那将节省大量处理时间，因为您只需要重新排序位置已更改的元素，您可以避免重新排序直到至少有一个元素移动。