计算机科学sorting与“真实”世界sorting
我在考虑用软件sortingalgorithm，以及可能的方法是克服O(nlogn)障碍。 我不认为从实际意义上可以更快地sorting，所以请不要以为我这样做。
这样说，似乎几乎所有的sortingalgorithm，软件必须知道每个元素的位置。 这是有道理的，否则，它将如何知道根据一些sorting标准来放置每个元素的位置？
但是当我把这个想法与现实世界交织在一起的时候，离心机根本不知道每个分子在密度分类时的位置。 事实上，它并不关心每个分子的位置。 然而，由于每个分子都遵循密度和引力定律，所以它可以在相当短的时间内将数万亿分之一的物质分类，这让我想到了这一点。
是否有可能在每个节点上有一些开销（某些值或方法加到每个节点上）来“强制”列表的顺序？ 像离心机一样，只有每个元素都关心它在空间中的相对位置（相对于其他节点）。 或者，这是否违反了计算中的一些规则？
我认为这里提出的一个重点是自然界的量子力学效应，以及它们如何同时应用于所有粒子。
也许古典计算机本质上限制sorting到O(nlogn)的领域，在这个领域，量子计算机可能能够跨越这个阈值成为并行运算的O(logn)algorithm。
离心机基本上是一个平行气泡sorting的观点似乎是正确的，其具有O(n)的时间复杂度。
我想下一个想法是，如果大自然可以sorting在O(n) ，为什么不能电脑？
编辑：我误解了一个离心机的机制，它似乎做了一个比较，一个大规模平行的那个。 但是有物理过程对被sorting的实体的属性进行操作，而不是比较两个属性。 这个答案涵盖了这种性质的algorithm。
离心机应用了一种sorting机制，它并不是通过元素之间的比较来实际工作，而是实际上通过每个单独元素上的特性（“离心力”）来隔离。 一些sortingalgorithm属于这个主题，特别是基数sorting 。 当这种sortingalgorithm是并行的，它应该接近离心机的例子。
一些其他的非比较sortingalgorithm是桶sorting和计数sorting 。 您可能会发现斗式sorting也符合离心机的一般概念（半径可以对应一个垃圾桶）。
另一个所谓的“sortingalgorithm”，其中每个元素被孤立地考虑在内，就是睡眠sorting 。 这里的时间，而不是离心力作为分选的大小。
计算复杂性总是根据一些计算模型来定义的。 例如，如果在Brainfuck中实现，则在典型计算机上的O （ n ）algorithm可能是O （2 n ）。
离心机计算模型具有一些有趣的特性; 例如：
- 它支持任意并行性; 无论解决scheme中有多less个粒子，它们都可以同时sorting。
- 它不是按质量给出严格的线性排列的粒子，而是非常接近（低能量）的近似。
- 检查结果中的单个粒子是不可行的。
- 不可能通过不同的属性对粒子进行sorting; 只有质量被支持。
鉴于我们没有能力在通用计算硬件中实现这样的东西，这个模型可能没有实际意义; 但仍然值得研究，看看有没有什么可以从中学到的。 非确定性algorithm和量子algorithm都是活跃的研究领域，例如，即使这两种algorithm都不是现在可以实现的。
诀窍在那里，你只有使用离心机sorting列表的概率。 和其他真实世界的sorting一样，你可以改变你对列表进行sorting的概率，但是如果不检查所有的值（primefaces），就不能确定。
考虑这个问题：“离心机运行多久？
如果你只运行它皮秒，你的样本可能比初始状态更lesssorting，或者如果你跑了几天，它可能是完全sorting。 但是，如果不实际检查内容，则不知道。
一个基于计算机的“sorting”的真实世界的例子是自主的无人驾驶飞机相互合作，称为“无人机群”。 无人驾驶飞机既可以作为个人也可以作为一个组进行沟通，并可以跟踪多个目标。 无人机共同决定哪些无人机将遵循哪些目标，明显需要避免无人机之间的碰撞。 早期的版本是无人驾驶飞机，在编队的时候通过方式转移，但编队可能会改变。
对于“sorting”，可以将无人机编程为以特定顺序形成线条或图案，最初以任何置换或形状释放，并且集体并行地它们将快速形成有序的线条或图案。
回到基于计算机的sorting，一个问题是有一个主存储器总线，并且没有办法让大量的对象并行地在内存中移动。
知道每个元素的位置
在磁带sorting的情况下，每个元素（logging）的位置只对“磁带”“已知”，而不是计算机。 基于磁带的sorting只需要一次处理两个元素，一种方式来表示磁带上的运行边界（文件标记或不同大小的logging）。
恕我直言，人们过度login（n）。 O（nlog（n））实际上是O（n）。 而你只需要O（n）来读取数据。
诸如quicksort之类的许多algorithm都提供了一种快速sorting元素的方法。 你可以实现快速sorting的变化，这在实践中会很快。
本质上所有的物理系统是无限平行的。 你可能在沙粒中有一堆primefaces，大自然有足够的计算能力来确定每个primefaces中每个电子应该在哪里。 所以如果你有足够的计算资源（O（n）处理器），你可以在log（n）时间内sortingn个数字。
来自评论：
-
给定一个具有k个元素的物理处理器，它可以达到至多O（k）的平行度。 如果你任意处理n个数字，它仍然会以与k相关的速率进行处理。 而且，你可以在物理上制定这个问题。 您可以创buildn个钢球，其重量与要编码的数量成正比，这可以通过理论上的离心机来解决。 但是在这里你使用的primefaces的数量与n成正比。 而在标准情况下，处理器中的primefaces数量有限。
-
另一种考虑这种方式的方法是，假设每个数字都附有一个小处理器，每个处理器可以和邻居进行通信，您可以在O（log（n））时间内对所有这些数字进行sorting。
大学gradle后，我在高中gradle后在办公室工作。 我曾在AP计算机科学学习过，包括sorting和search 。
我将这些知识应用于几个我可以记得的物理系统：
自然合并sorting开始…
系统打印的多部分表格包括需要在一堆抽屉中存档的文件卡大小的撕下。
我从一堆堆开始，把堆放在一起。 第一步是拿起5个左右，几个足够轻松放置在你的手中。 把分类好的包裹放下，使每个堆叠交叉以保持它们分离。
然后， 合并每一对堆栈，生成一个更大的堆栈。 重复，直到只有一个堆栈。
插入sorting完成
将已sorting的纸牌存档更容易，因为每一张纸牌下一张纸牌都位于同一个打开的纸盒的下方。
基数sorting
没有人知道我是如何做得这么快，尽pipe一再试图教它。
需要对一大盒检查存根（打卡的大小）进行sorting。 它看起来像在一张大桌子上玩纸牌 – 交易，叠加，重复。
一般来说
30年前，我注意到你在问什么：这些想法直接转换到物理系统，因为比较和处理logging有相对的成本，而且caching水平也很高。
超出了人们所理解的等值
我记得关于你的话题的一篇文章，它提出了意大利面条的种类 。 您可以修剪一些干面条以指示关键值，并将其标记为loggingID。 这是O（n），简单地处理每个项目一次。
然后你抓住捆绑，并点击桌子上的一端。 它们在底部边缘alignment，现在它们被分类。 你可以轻松地取下最长的一个，重复一遍。 读出也是O（n）。
在“现实世界”中，有两件事情与algorithm不相符。 首先，alignment边缘是一个并行操作。 每个数据项也是一个处理器（物理定律适用于它）。 所以，一般来说，你用n来扩展可用的处理，基本上把经典的复杂度除以n的一个因子。
其次，如何alignment边缘完成一个sorting？ 真正的sorting是在读出来，让你find最长的一步，即使你没有比较所有的人发现最长的。 再次除以n的因子，find最大的就是O（1）。
另一个例子是使用模拟计算：物理模型“立即”解决了问题，准备工作是O（n）。 原则上，计算是根据交互组件的数量进行缩放，而不是准备项目的数量。 所以计算与n2成比例。 我想到的例子是一个加权的多因素计算，这是通过在地图上打孔，从穿过孔的弦悬挂重物，并将所有弦收集在环上来完成的。
sorting仍然是O（n）总时间。 它比这更快是因为并行化 。
您可以将离心机视为n个primefaces的Bucketsort ，在n个核心（每个primefaces充当处理器）上并行化。
你可以通过并行化来更快的sorting，但是由于处理器数量有限，O（n / C）仍然是O（n）（CPU通常<10核心，GPU <6000）
离心机没有对节点进行分类，它适用于施加一个力量，然后他们平行反应。 所以如果你要实现一个气泡sorting，每个节点根据它的“密度”来平行移动，你需要一个离心机的实现。
请记住，在现实世界中，可以运行大量的并行任务，在计算机中，可以有最多的实际并行任务，等于物理处理单元的数量。
最后，你也将被限制访问元素列表，因为它不能被两个节点同时修改。
是否有可能在每个节点上有一些开销（某些值或方法加到每个节点上）来“强制”列表的顺序？
当我们使用计算机程序sorting时，我们select一个正在sorting的值的属性。 这通常是数字的大小或字母顺序。
就像离心机一样，每个元素只关心它在空间的相对位置（相对于其他节点）
这个比喻恰如其分地提醒我简单的泡沫sorting。 在每次迭代中，数量如何变小。 像你的离心机逻辑。
所以要回答这个问题，难道我们实际上在软件sorting中做了这样的事吗？
首先，比较两个不同的上下文，一个是逻辑（计算机），另一个是物理（到目前为止）已经certificate，我们可以使用math公式来模拟它的一些部分，我们作为程序员可以使用这个公式来模拟（某些部分）逻辑工作中的物理（例如游戏引擎中的物理引擎）。
其次，在物理学几乎不可能的计算机（逻辑）世界中，我们有一些可能性，例如我们可以访问存储器，并在每个时间find每个实体的确切位置，但是在物理学中这是海森堡不确定性原理的一个巨大问题。
第三如果你想将离心机及其在现实世界中的操作映射到计算机世界，就像某人（上帝）已经给你一台应用了所有物理规则的超级计算机，并且正在对它进行小的sorting使用离心机），并说你的sorting问题已经解决o（n）你忽略了在后台进行的巨大的物理模拟…
另一个观点是，你用离心机描述的东西类似于所谓的“意大利面sorting”（ https://en.wikipedia.org/wiki/Spaghetti_sort ）。 假设你有一盒不同长度的未煮过的意大利细面条。 握住他们的拳头，松开你的手垂直降低他们的两端都搁在一张水平的桌子上。 繁荣！ 他们按高度sorting。 O（恒定）时间。 （或者O（n），如果你包括把身高的棒子拿出来放在一个…意大利面条架上，我猜？）
你可以在那里注意到意大利细面条的数量是O（常数），但是由于意大利细面条的声速是有限的，所以在最长的一条细条的长度上是O（n）。 所以没有什么是免费的。
考虑一下：“离心机sorting” 真的比较好吗？ 想想当你放大时会发生什么。
- 试pipe必须变得越来越长。
- 沉重的东西必须进一步深入到底。
- 惯性的时刻增加，需要更多的动力和更长的时间加速到分拣速度。
离心机sorting也是值得考虑的其他问题。 例如，您只能在狭窄的尺寸上操作。 一个计算机sortingalgorithm可以处理从1到2 ^ 1024以上的整数，没有汗水。 把重量是氢primefaces2 ^ 1024倍的东西放入离心机中，好吧，这是一个黑洞，星系已被破坏。 algorithm失败。
当然，这里真正的答案是计算复杂性是相对于一些计算模型，正如其他答案中提到的。 而“离心机sorting”在通用计算模型（例如RAM模型或IO模型或multitape图灵机）的背景下是没有意义的。
