algorithm - 计算机科学中的排序与 'real' 世界中的排序

Question

我在考虑软件中的排序算法，以及克服 O(nlogn) 障碍的可能方法。我不认为在实际意义上可以更快地排序，所以请不要认为我可以。

话虽如此，似乎对于几乎所有的排序算法，软件都必须知道每个元素的位置。这是有道理的，否则，它怎么知道根据某种排序标准将每个元素放在哪里？

但是当我将这种想法与现实世界进行交叉时，离心机在按密度“分类”分子时并不知道每个分子处于什么位置。事实上，它并不关心每个分子的位置。然而，由于每个分子都遵循密度和引力定律，它可以在相对较短的时间内分拣数万亿件元素 - 这让我开始思考。

是否有可能在每个节点上增加一些开销(将某些值或方法附加到每个节点上)来“强制”列表的顺序？有点像离心机，其中只有每个元素关心它在空间中的相对位置(相对于其他节点)。或者，这是否违反了某些计算规则？

我认为这里提出的重点之一是自然界的量子力学效应以及它们如何同时平行应用于所有粒子。

也许经典计算机本质上将排序限制在 O(nlogn) 的范围内，而量子计算机可能能够跨越该阈值进入 O(logn) 算法并行行动。

离心机基本上是一个 parallel bubble sort似乎是正确的，其时间复杂度为 O(n)。

我想下一个想法是，如果大自然可以在 O(n) 中排序，为什么计算机不能？

Answer 1

编辑:我误解了离心机的机制，它似乎做了一个比较，一个大规模并行的比较。但是，存在对被排序实体的属性进行操作而不是比较两个属性的物理过程。这个答案涵盖了具有这种性质的算法。

离心机应用了一种排序机制，该机制实际上并不是通过元素之间的比较来工作，而是实际上是通过每个单独元素的属性(“离心力”)来隔离。一些排序算法属于这个主题，尤其是Radix Sort .当这种排序算法被并行化时，它应该接近离心机的例子。

其他一些非比较排序算法是Bucket sort和 Counting Sort .您可能会发现桶排序也符合离心机的一般概念(半径可以对应于垃圾箱)。

另一种所谓的“排序算法”，其中每个元素都被认为是孤立的，是 Sleep Sort .这里时间而不是离心力作为分选的大小。