blocks|key|1290016|text|你刚刚重申了这个问题。计算引力效应的顺序最多有O的排序算法，你想要击败的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1290017|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

You've just restated the problem. Calculating the order of the gravitational effects will have, at best, the O of the sort algorithms you're trying to beat.

blocks|key|1521496|text|一旦你计算了所有的落地时间，你仍然需要对这些值进行排序。你并没有真正得到什么，你只是在做一些额外的不必要的计算后，对不同的数字进行排序。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1521497|编辑：哇哦。忘了物理101。当然，他们都会同时攻击。:)|offset|length|style|BOLD|1521498|任何类似的建模都只是将一个排序问题转化为另一个排序问题。你什么也得不到。|1521499|entityMap^0|0|0|2|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@$D|N|E|O|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

Once you've calculated all the times they take to hit the ground, you'll still have to sort those values. You're not really gaining anything, you're just sorting different numbers after performing some extra unnecessary calculation.

EDIT: Whoops. Forgot physics 101. Of course they'll all hit at the same time. :)

Any sort of modeling like this just transforms one sorting problem into another one. You won't gain anything.

blocks|key|1521549|text|引力计算仅在现实世界中是免费的。在程序中，你需要给它建模。它将是复杂度最小的另一个n。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1521550|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Gravitation calculation is free of charge only in real world. In programm you need to model it. It will be another n in complexity minimum

blocks|key|1521562|text|这个想法看起来很简单，但是在这个例子中，真实世界和模型世界之间的区别是，在现实世界中，一切都是并行发生的。要像您所描述的那样对引力排序进行建模，您必须首先在一个单独的线程上考虑每个对象，并以线程安全的方式将它们按完成顺序添加到列表中。实际上，就排序性能而言，您可能只是在时间上使用快速排序，或者因为它们在相同的距离上下降的速度。然而，如果你的公式与质量成正比，你就跳过所有的公式，对质量进行排序。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1521563|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

The idea might seem simple, but the difference between the real world and the modeled one in this case is that in the real world everything is happening in parallel. To model the gravitational sort as you describe you would have to start by thinking each object on a separate thread with a thread safe way to add them to a list in the order they finish. Realistically in terms of sorting performance you would probably just use a quick sort on the times, or since they are at the same distance the rate of falling. However if your formula is proportional to the mass, you'd just skip all that and sort the mass.

blocks|key|1290048|text|在虚构的“引力计算机”中，这种排序需要O(1)来求解。但是有了我们所知道的真正的电脑，你的横向想法就不会有帮助了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1290049|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In a fictious "gravitational computer" this kind of sorting would take O(1) to be solved. But with the real computers like we know it, your lateral thought wouldn't help.

blocks|key|1290055|text|忽略其他人提到的所有缺陷，本质上这归结为O(n%5E2)算法，而不是O(n)。你必须遍历所有的“球”，找到“最重的”或“最大的”，然后把它推到列表上，然后漂洗和重复。也就是说，要找到第一个击中地面的，你必须遍历整个列表，如果是最后一个，它将花费O(n)时间，第二个可能需要O(n-1)等等。但更糟糕的是，每次你都要执行一些数学运算，只是为了计算一些无用的“时间”值，当你本来可以对你感兴趣的值进行排序的时候。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1290056|entityMap^0|K|6|W|4|3C|4|3Q|6|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]|$9|M|A|N|B|C]|$9|O|A|P|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|Q|8|@]|D|@]|E|$]]]|G|$]]

Ignoring all the flaws that everyone else has mentioned, essentially this boils down to an <code>O(n^2)</code> algorithm, not <code>O(n)</code>. You'd have to iterate over all the "spheres", find the "heaviest" or "biggest" one, and then push it onto a list, then rinse and repeat. i.e., to find the one that hits the ground first, you have to iterate over the whole list, if it's the last one, it'd take <code>O(n)</code> time, the second would could take <code>O(n-1)</code>, etc... but worse than that, you have to perform a bunch of mathematical operations each time just to calculate some useless "time" value when you could have sorted on the value you were interested in in the first place.

blocks|key|1521675|text|问题是，尽管OOP的一个想法可能是对现实世界建模，但这并不意味着在现实世界中物体所需的时间与用计算机模拟它所需的时间之间存在直接的对应关系。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1521676|想象一下您的过程所需的实际步骤：|1521677|必须为数据集中的每个项构造一个对象。在大多数现代硬件上，这本身就需要迭代，因此您的策略O(n)充其量也是如此。|ordered-list-item|1521678|每个物体都需要模拟重力的影响。同样，实现这一点的最明显、最直接的方法是迭代。|1521679|在您的编程模型中，每个对象降落在“地球”表面的时间必须被捕获，并且通过一些特定于实现的机制，相应的对象将需要被插入到一个有序的列表中。|1521680|考虑到这一问题，进一步引入了额外的复杂因素。扪心自问:你需要将这些物体定位到多高的位置才能启动？明显地足够高，以至于最大的物体实际上会坠落；也就是说，离地球更远，比最大物体的半径更远。但你怎么知道那有多远？您需要首先确定集合中最大的对象；这同样(可能)需要迭代。另外，人们可能会想象，这种模拟可以是多线程的，以尝试模拟物体实际下落的概念的实时行为；但是，您会发现自己试图向集合中添加项(显然需要花费非零时间的操作)，同时可能会检测到新的碰撞。因此，这也会造成线程问题。|1521681|简而言之，我很难想象这个想法是如何在没有特殊硬件的情况下使用OOP正确实现的。尽管如此，这确实是个好主意。它让我想起了珠子分类--这个算法虽然和你的想法不一样，但它也是一种排序解决方案，它利用了重力这一物理概念，而且毫不奇怪，需要专门的硬件。|offset|length|1521682|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Bead_sort^0|0|0|0|0|0|0|1N|4|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Z|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|10|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|11|8|@]|9|@]|A|$]]|$1|I|3|J|5|F|7|12|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|13|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|14|8|@]|9|@$O|15|P|16|1|17]]|A|$]]|$1|Q|3|-4|5|6|7|18|8|@]|9|@]|A|$]]]|R|$S|$5|T|U|V|A|$W|X]]]]

The thing is, though one of the ideas of OOP may be to model the real world, that doesn't mean there's a direct correspondence between how long something takes in the real world and how long it would take to simulate it with a computer.

Imagine the actual steps required for your procedure:

<ol>
<li>An object has to be constructed for every item in your set of data. On most modern hardware, this alone would require iteration and would therefore make your strategy O(n) at best.</li>
<li>The effect of gravity would need to be simulated, for each object. Again, the most obvious, straightforward way to implement this would be to iterate.</li>
<li>The time that each object lands on the surface of the "Earth" in your programming model would have to be captured and, via some implementation-specific mechanism, the corresponding object would need to be inserted into an ordered list as a result.</li>
</ol>

Considering the problem further introduces additional complications. Ask yourself this: how high up do you need to position these objects to start? Obviously high enough so that the largest one actually falls; i.e., farther from the Earth than the radius of the largest object. But how do you know how far that is? You'd need to first determine the largest object in the collection; this, again, would (probably) require iterating. Also, one might imagine that this simulation could be multithreaded to attempt to simulate the real-time behavior of the notion of objects actually falling; but then you will find yourself attempting to add items to a collection (an operation which obviously takes a non-zero amount of time) potentially at the same time that new collisions are being detected. So this will create threading issues as well.

In short, I have trouble imagining how this idea could be properly implemented simply using OOP without special hardware. That said, it really is a good idea. It reminds me, in fact, of <a href="http://en.wikipedia.org/wiki/Bead_sort" rel="noreferrer">Bead Sort</a>--an algorithm which, though not the same as your idea, is also a sorting solution that takes advantage of the very physical concept of gravity and, not surprisingly, requires specialized hardware.

blocks|key|3045640|text|它应该是绝对只有你应该有适当的硬件支持为它。否则这听起来是个很酷的主意。希望有人提出一个IEEE文件，使这个疯狂的梦想可视化。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3045641|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

It should be definitely only you should have proper hardware supported for it. Otherwise this sounds a very cool idea. Hope someone presents an IEEE paper to make this crazy dream visualized.

blocks|key|1521753|text|几周前我也在想同样的事情。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1521754|我想使用Phys2D库来实现它。这可能不实际，但只是为了好玩。您还可以为对象分配负重来表示负数。使用phys2d库，您可以定义重力，使负重物体到达屋顶，具有正重量的对象将从.Then下降，将所有物体安排在地板与屋顶之间的中间，地板与屋顶之间的距离相同。假设您有一个结果数组r[]+of+length=number的对象。然后，每当一个对象接触到屋顶时，您在数组r的开头添加它并增加计数器，下一次当一个对象接触到屋顶时，您可以在r1添加它，每次当一个对象到达地板时，您将它添加到数组rr.ength-1的末尾，下次将其添加到rr.ength-2时。最后，没有移动的对象(中间保持浮动)可以添加到数组的中间(这些对象是0)。|offset|length|1521755|这不是有效的，但可以帮助您实现您的想法。|1521756|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cokeandcode.com/phys2d/^0|0|4|6|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@$D|R|E|S|1|T]]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]]]

Some weeks ago I was thinking about the same thing.

I thought to use <a href="http://www.cokeandcode.com/phys2d/" rel="nofollow noreferrer">Phys2D</a> library to implement it. It may not be practical but just for fun. You could also assign negative weights to the objects to represent negative numbers. With phys2d library you can define the gravity so objects with negative weight will go to the roof and objects with positive weight will fall down .Then arrange all objects in the middle between the floor and roof with the same distance between floor and roof. Suppose you have a resulting array r[] of length=number of objects. Then every time an object touches the roof you add it at the beginning of the array r[0] and increment the counter, next time an object touches the roof you add it at r&#91;1], every time an object reaches the floor you add it at the end of the array r[r.length-1], next time you add it at r[r.length-2]. At the end objects that didn't move(stayed floating in the middle) can be added in the middle of the array(these objects are the 0's).

This is not efficient but can help you implement your idea.

blocks|key|3045722|text|嗯。重力排序。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3045723|忽略你的重力模型是错误的，让我们看看这个想法会给我们带来什么。|3045724|物理现实有10%5E80处理器。|3045725|如果有N/2处理器对N个对象进行排序，那么排序的实际下界就是log(N)。|3045726|如果您有多个CPU核心可用，就没有理由不能在多个线程上运行mergesort。|3045727|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|O|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|P|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

Hmmmm. Gravity sort.

Ignoring your specific model of gravity is wrong, let's see where this idea takes us.

Physical reality has 10^80 processors.

The actual lower bounds of sort is known to be log(N) if you have N/2 processors to sort N objects.

If you have several CPU cores available there's no reason you can't run mergesort on several threads.

blocks|key|3045772|text|我认为这个问题可以变得更简单:你想把球的底部放在不同的高度，这样当球落在相同的重力下时，最大的球就会先落地，第二大的球落地，等等。这基本上相当于用线，而不是spheres...in，在这种情况下，你只需要说heightOffTheGround+=+MAX_VALUE+-质量。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3045773|你也不需要担心time...since上的加速度--不管它们的速度有多快，或者是现实物理，你可以给出它们的初始速度x，然后从那里开始。|3045774|问题是，我们实际上只是重新描述了这个问题，并像这样解决了它(伪代码)：|3045775|int[]+sortedArray;+//+empty
int[]+unsortedArray;+//+full+of+stuff
int+iVal+=+MAX_INT_VALUE;
while+(true)
{
++++foreach+(currentArrayValue+in+sortedArray)
++++{
++++++++if+(iVal+=+current+array+value
++++++++{
++++++++++++put+it+in+my+sortedArray
++++++++++++remove+the+value+from+my+unsortedArray
++++++++}
++++}
++++if+(unsortedArray+is+empty)
++++{
++++++++break;++//+from+while+loop
++++}+
++++iVal--
}|code-block|syntax|javascript|3045776|问题是，要运行物理引擎，必须遍历每个时间单元，这将是O(1)...with，非常，系统将运行的δ值的很大的constant...the常量。缺点是，对于这些增量值中的绝大部分，您基本上不会接近答案:在任何给定的迭代中，很可能所有的球面/行/任何有moved...but的东西都不会命中。|offset|length|style|BOLD|3045777|你可以试着说，好吧，让我们跳过很多中间的步骤，然后跳到前面，直到一个击中！但这意味着您必须知道哪一个是largest...and，您又回到了排序问题上。|3045778|entityMap^0|0|0|0|0|12|2|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|V|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|W|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|X|8|@]|9|@]|A|$I|J]]|$1|K|3|L|5|6|7|Y|8|@$M|Z|N|10|O|P]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|11|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

I think the problem can be made simpler like this: you want to put the bottoms of the spheres at different heights so that when dropped at identical gravities the largest will hit the ground first, second largest second, etc. This is essentially equivalent to using lines rather than spheres...in which case you can just say that heightOffTheGround = MAX_VALUE - mass.

You also don't need to worry about acceleration over time...since you don't care how fast they are going or realistic physics, you can give them all an initial velocity x, and go from there.

The problem is then that we've essentially just restated the problem and solved it like this (pseudocode):

<pre><code>int[] sortedArray; // empty
int[] unsortedArray; // full of stuff
int iVal = MAX_INT_VALUE;
while (true)
{
 foreach (currentArrayValue in sortedArray)
 {
 if (iVal = current array value
 {
 put it in my sortedArray
 remove the value from my unsortedArray
 }
 }
 if (unsortedArray is empty)
 {
 break; // from while loop
 } 
 iVal--
}
</code></pre>

The problem is that to run the physics engine, you've got to iterate over each time unit, and that will be O(1)...with a very large constant...the constant number of delta values that the system will run on. The drawback is that for the very large majority of these delta values, you will essentially be getting no closer to the answer: on any given iteration, it is very likely that all the spheres/lines/whatever will have moved...but none will hit. 

You could try to just say, well, let's skip a lot of intermediary steps and just jump ahead until one hits! But that means that you have to know which one is the largest...and you're back to the sorting issue.

blocks|key|1290191|text|我会调整一下你的想法。我们确实有我们的物体，但它们在重量上没有区别，但在速度上是不同的。所以，在开始的时候，所有的物体都在起跑线和起跑线上对齐，它们都会以各自的速度移动到终点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1290192|足够清晰:+finish中的第一个对象会发出一个信号，表示它就在那里。你捕捉到信号，然后写信给结果文件。|1290193|好吧，所以你要模拟一下。|1290194|我们以您的字段长度为L=1。使用步骤大小∆t，每个N对象一次移动一段vᵢ∙∆t。这意味着每个对象在到达finish之前都需要sᵢ+=+L+/+(vᵢ∙∆t)步骤。|offset|length|style|CODE|1290195|现在的重点是，为了区分速度非常接近的两个对象，您需要对所有对象都有不同的步长。|1290196|现在，在最佳的情况下，这意味着对象1在一个步骤中完成，对象2在两个步骤中完成等等。因此，步骤的总数是S+=+1+%2B+2+%2B+…+%2B+N+=+N∙(N+%2B+1)/2。这是N∙N的顺序。|BOLD|1290197|如果这不是最好的情况，而且速度不是相当接近，您将不得不降低步长，实际上迭代了很多次。|1290198|entityMap^0|0|0|0|A|3|K|2|P|1|Y|5|1Q|G|0|0|4|2|1E|V|2C|3|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|V|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|W|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|X|8|@$H|Y|I|Z|J|K]|$H|10|I|11|J|K]|$H|12|I|13|J|K]|$H|14|I|15|J|K]|$H|16|I|17|J|K]]|9|@]|A|$]]|$1|L|3|M|5|6|7|18|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|19|8|@$H|1A|I|1B|J|P]|$H|1C|I|1D|J|K]|$H|1E|I|1F|J|K]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1G|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|1H|8|@]|9|@]|A|$]]]|T|$]]

I’ll adapt your idea a little. We do have our objects but they don’t differ in weight, but in speed. So, at the beginning all objects are aligned at the starting line and on the starting shot, they’ll all move with their respective velocities to the finish.

Clear enough: First object in finish will emit a signal, saying it is there. You catch the signal and write to the results paper who it was.

Okay, so you’ll want to simulate that.

We take the length of your field to be <code>L=1</code>. With step size <code>∆t</code> each of your <code>N</code> objects moves a length of <code>vᵢ∙∆t</code> at a time.
That means each object needs <code>sᵢ = L / (vᵢ∙∆t)</code> steps before reaching the finish.

The point is now, in order to distinguish between two objects with very close speeds, you’ll need to have a different step size for all of your objects.

Now, in the best case, this means that object 1 finishes in one step, object 2 in two and so on. Therefore, the total number of steps is <code>S = 1 + 2 + … + N = N∙(N + 1)/2</code>. This is of order <code>N∙N</code>.

If it’s not the best case and the velocities are not equally close to each other, you’ll have to lower the step size and in effect iterate many more times.

blocks|key|1521906|text|来自https://stackoverflow.com/questions/2489190/gravity-sort-is-this-possible-programatically/2496039#2496039
我会调整一下你的想法。我们确实有我们的物体，但它们在重量上没有区别，但在速度上是不同的。所以，在开始的时候，所有的物体都在起跑线和起跑线上对齐，它们都会以各自的速度移动到终点。
足够清晰:+finish中的第一个对象会发出一个信号，表示它就在那里。你捕捉到信号，然后写信给结果文件。|type|blockquote|depth|inlineStyleRanges|entityRanges|offset|length|data|1521907|我把它简化一步，说这些对象是随机正整数。当它们接近于零时，我们希望按升序对它们进行排序，因此它们与零d之间有一个距离，它最初等于整数本身。|unstyled|style|CODE|1521908|假设模拟发生在离散的时间步骤中，即帧，在每个帧中，每个对象的新距离是：d+=+d+-+v和一个对象在其d+≤+0时被添加到列表中。这是一个减法和一个条件。每个对象有两个离散的步骤，所以计算似乎是O(n)：线性的。|1521909|问题是，它只对一帧是线性的！它被乘以完成所需的帧数f。模拟本身是O(nf)：二次型。|BOLD|1521910|然而，如果我们以帧的持续时间作为参数t，则可以以反比的方式影响帧f的数目。我们可以增加t以减少f，但这是以牺牲精度为代价的，我们增加的t越多，两个对象在同一时间框架内完成的概率就越大，因此被列为等价对象，即使它们不是。因此，我们得到了一个精度可调的算法(在大多数有限元模拟环境中是如此)。|1521911|通过将其转化为adaptive%2Brecursive算法，我们可以进一步改进它。在人类代码中，这将是：|1521912|function:+FESort:+arguments:+OriginalList,+Tolerance
++define+an+empty+local+list:+ResultList

++while+OriginalList+has+elements
++++define+an+empty+local+list:+FinishedList
++++iterate+through+OriginalList
++++++decrement+the+distance+of+each+object+by+Tolerance
++++++if+distance+is+less+than+or+equal+to+zero,+move+object+from+OriginalList+to+FinishedList

++++check+the+number+of+elements+in+FinishedList
++++++when+zero
++++++++set+Tolerance+to+double+Tolerance
++++++when+one
++++++++append+the+only+element+in+FinishedList+to+ResultList
++++++when+more
++++++++append+the+result+of+FESort+with+FinishedList+and+half+Tolerance+to+ResultList
++
++return+ResultList|code-block|syntax|javascript|1521913|我想知道是否有真正的类似的实现为某人工作。|1521914|令人感兴趣的主题:)|1521915|PS。上面的伪码是我对伪码的理解，如果有伪码，请随时用更清晰或一致的方式重写。|1521916|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/2489190/gravity-sort-is-this-possible-programatically/2496039#2496039^0|2|2X|0|0|1E|1|0|Z|9|1F|5|0|7|2|P|1|0|I|1|W|1|17|1|1B|1|1V|1|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1A|8|@]|9|@$A|1B|B|1C|1|1D]]|C|$]]|$1|D|3|E|5|F|7|1E|8|@$A|1F|B|1G|G|H]]|9|@]|C|$]]|$1|I|3|J|5|F|7|1H|8|@$A|1I|B|1J|G|H]|$A|1K|B|1L|G|H]]|9|@]|C|$]]|$1|K|3|L|5|F|7|1M|8|@$A|1N|B|1O|G|M]|$A|1P|B|1Q|G|H]]|9|@]|C|$]]|$1|N|3|O|5|F|7|1R|8|@$A|1S|B|1T|G|H]|$A|1U|B|1V|G|H]|$A|1W|B|1X|G|H]|$A|1Y|B|1Z|G|H]|$A|20|B|21|G|H]]|9|@]|C|$]]|$1|P|3|Q|5|F|7|22|8|@]|9|@]|C|$]]|$1|R|3|S|5|T|7|23|8|@]|9|@]|C|$U|V]]|$1|W|3|X|5|F|7|24|8|@]|9|@]|C|$]]|$1|Y|3|Z|5|F|7|25|8|@]|9|@]|C|$]]|$1|10|3|11|5|F|7|26|8|@]|9|@]|C|$]]|$1|12|3|-4|5|F|7|27|8|@]|9|@]|C|$]]]|13|$14|$5|15|16|17|C|$18|19]]]]

<blockquote>
from <a href="https://stackoverflow.com/questions/2489190/gravity-sort-is-this-possible-programatically/2496039#2496039">Debilski's answer</a>:
I’ll adapt your idea a little. We do
have our objects but they don’t differ
in weight, but in speed. So, at the
beginning all objects are aligned at
the starting line and on the starting
shot, they’ll all move with their
respective velocities to the finish.
Clear enough: First object in finish
will emit a signal, saying it is
there. You catch the signal and write
to the results paper who it was
</blockquote>
I'd simplify it a step further and say these objects are random positive integers. And we want to sort them in an ascending order as they approach zero, so they have a distance from zero <code>d</code> which initially is equal to the integer itself.
Assuming the simulation takes place in discrete time steps i.e. frames, in every frame, every object's new distance would be: <code>d = d - v</code> and an object would get added to the list when its <code>d ≤ 0</code>. That is one subtraction and one conditional. Two discrete steps for each object, so the calculations seem to be O(n): linear.
The catch is, it is linear for one frame only! It is multiplied by the number of frames <code>f</code> required to finish. The simulation itself is O(nf): quadratic.
However, if we take the duration of a frame as the argument <code>t</code> we get the ability to affect the number of frames <code>f</code> in an inversely proportional manner. We can increase <code>t</code> to reduce <code>f</code> but this comes at the cost of accuracy, the more we increase <code>t</code>, the more the probability that two objects will finish in the same time frame therefore be listed as equivalent, even if they are not. So we get an algorithm with adjustable accuracy (as it is in most finite element simulation contexts)
We can further refine this by turning it into an adaptive+recursive algorithm. In human code it would be:
<pre><code>function: FESort: arguments: OriginalList, Tolerance
 define an empty local list: ResultList

 while OriginalList has elements
 define an empty local list: FinishedList
 iterate through OriginalList
 decrement the distance of each object by Tolerance
 if distance is less than or equal to zero, move object from OriginalList to FinishedList

 check the number of elements in FinishedList
 when zero
 set Tolerance to double Tolerance
 when one
 append the only element in FinishedList to ResultList
 when more
 append the result of FESort with FinishedList and half Tolerance to ResultList
 
 return ResultList
</code></pre>
I'm wondering if there's any real similar implementation that works for someone.
Interesting subject indeed :)
PS. The pseudocode above is my idea of pseudocode, please feel free to rewrite it in a more legible or conformant way if there is one.

blocks|key|1291965|text|事实上，有一种非常著名的排序算法叫做意大利面排序，它和你的排序有点相似。你可以在网上查看其中的一些分析。例如在[医]理论上。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1291966|​|1291967|📷|atomic|1291968|1291969|entityMap|0|LINK|mutability|MUTABLE|url|https://cstheory.stackexchange.com/questions/7042/is-spaghetti-sort-really-on-even-as-a-thought-experiment|1|IMAGE|IMMUTABLE|imageUrl|https://developer.qcloudimg.com/http-save/yehe-900000/c0422f127e661f14e04afe29107a9817.jpg|imageAlt^0|1J|5|0|0|0|0|1|1|0|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@$A|Y|B|Z|1|10]]|C|$]]|$1|D|3|E|5|6|7|11|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|12|8|@]|9|@$A|13|B|14|1|15]]|C|$]]|$1|I|3|E|5|6|7|16|8|@]|9|@]|C|$]]|$1|J|3|-4|5|6|7|17|8|@]|9|@]|C|$]]]|K|$L|$5|M|N|O|C|$P|Q]]|R|$5|S|N|T|C|$U|V|W|-4]]]]

There is actually a quite famous sorting algorithm called Spaghetti sort which is sort of similar to yours.
You can check out some of the many analyses of it on the web. e.g. on <a href="https://cstheory.stackexchange.com/questions/7042/is-spaghetti-sort-really-on-even-as-a-thought-experiment">cstheory</a>.

<img src="https://i.stack.imgur.com/eycfh.jpg" alt="spaghetti">

blocks|key|1290262|text|我认为很好地提到/参考：P与NP之间的关系与自然有效解决NP问题的能力有什么关系？排序是O(nlog(n))，为什么不尝试解决NP难题呢？|type|ordered-list-item|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1290263|根据物理物体的定律，物体与引力常数的比例是可以忽略不计的。|1290264|模拟物理过程会影响实际的时间复杂度。|1290265|unstyled|entityMap|0|LINK|mutability|MUTABLE|url|https://cs.stackexchange.com/questions/11026/what-is-the-relation-between-p-vs-np-and-natures-ability-to-solve-np-problems|1|http://en.wikipedia.org/wiki/Gravitational_constant^0|18|A|C|T|0|0|D|4|1|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@$9|V|A|W|B|C]]|D|@$9|X|A|Y|1|Z]]|E|$]]|$1|F|3|G|5|6|7|10|8|@]|D|@$9|11|A|12|1|13]]|E|$]]|$1|H|3|I|5|6|7|14|8|@]|D|@]|E|$]]|$1|J|3|-4|5|K|7|15|8|@]|D|@]|E|$]]]|L|$M|$5|N|O|P|E|$Q|R]]|S|$5|N|O|P|E|$Q|T]]]]

<ol>
<li>I believe it is nice to mention/refer to: <a href="https://cs.stackexchange.com/questions/11026/what-is-the-relation-between-p-vs-np-and-natures-ability-to-solve-np-problems">What is the relation
between P vs. NP and Nature's ability to solve NP problems
efficiently?</a>
Sorting is <code>O(nlog(n))</code>, why not trying to solve NP-hard problems?</li>
<li>By the laws of physics objects fall with proportions to the
<a href="http://en.wikipedia.org/wiki/Gravitational_constant" rel="nofollow noreferrer">gravitational constant</a> the mass is negligible.</li>
<li>Simulating a physical process can affect the actual time complexity.</li>
</ol>

blocks|key|1291991|text|分析：(1)所有球心在开始时都是对齐的(2)+==>质量越大，==>半径越大，==>距地面越低(3)在“真空”相同加速度=相同速度演化的==>相同距离下，对于中心==>，球体在概念上会更早地撞击地面==>，如果球体撞击地面时能发出识别信号%2B命中时间，那么好的物理技术是可行的。wich将给排序列表Practically...not一种“好的”数字技术|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1291992|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Analyse : 
(1) All centers of spheres are aligned at start
(2) greater number ==> mass higher ==> radius greater ==> distance to the ground lower
(3) in 'vacuum' same acceleration = same speed evolution ==> same distance for the center ==> how greater de radius...how earlier the sphere will hit the ground
==> conceptually OK, good physical technique if when a sphere hit the ground it can send an indentification signal + hit time ... wich will give the sorted list
Practically...not a 'good' numeric technique

I've been thinking recently on using the Object Oriented design in the sorting algorithm. However I was not able to find a proper way to even come closer in making this sorting algorithm that does the sorting in O(n) time. 

Ok, here is what I've been thinking for a week. I have a set of input data. I will assign a mass to each of the input data (assume input data a type of <code>Mass</code> and a type of <code>Sphere</code>. If we assume all objects to be perfectly spherical objects with shapes proportional to their mass, the heaviest one touches the ground first.). I will be placing all my input data in the space all at same distance from earth. And I will make them free fall. According to gravitational law, the heaviest one hits the ground first. And the order in which they hit will give me the sorted data. This is funny in some way, but underneath I feel that this should be possible using the OO that I have learnt till date

Is it really possible to make a sorting technique that uses gravitational pull like scenario or am I stupid/crazy?

Edit: Turns out all objects hit the ground at the same time hence I introduced the spherical object concept.

Gravity Sort : Is this possible programmatically?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

最近我一直在考虑在排序算法中使用面向对象的设计。然而，我无法找到一种适当的方法来使这种排序算法更接近于在O(n)时间内进行排序。好吧，这是我一个星期以来一直在想的事情。我有一组输入数据。我将为每个输入数据分配一个质量(假设输入数据为Mass类型和Sphere类型。如果我们假设所有物体都是完美的球形物体，形状与其质量成正...

问重力排序:这有可能是通过编程实现的吗？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问重力排序:这有可能是通过编程实现的吗？EN