对链表进行简单排序

我想创建一个带有顺序序列（整数属性）的双向链表，这样按顺序顺序进行排序可以创建一个实际上等价于链接列表的数组。对链表进行简单排序

given: a <-> b <-> c 

a.index > b.index 
b.index > c.index

该索引将需要有效地处理任意数量的插入。

有没有一种已知的算法来完成这个？ 问题是当列表变大并且索引序列已经打包时。在这种情况下，必须对列表进行扫描以恢复松弛。我只是不确定应如何完成此操作。理想情况下，会有某种自动平衡，因此这种借贷既快又少。

将所有左侧或右侧indecies更改为1以腾出空间插入的天真解决方案是O（n）。

我更喜欢使用整数，因为我知道数字在浮点上往往不太可靠，因为在大多数实现中它们接近零。

来源

2016-12-06 Josiah

为什么哦为什么dlinked列表？为什么不[平衡树]（https://en.wikipedia.org/wiki/https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree#Implementations）？ O（log（N））操作在增长/减少时没有问题。 –

“将所有左侧或右侧indecies改为1以腾出空间插入的天真解决方案是O（n）。”如果你真的坚持一个“分页*分页解决方案”（无论出于何种原因），而不是分散所有页面的松散，你可以简单地分割你想插入的页面，但是页面达到了它的填充因子。 –

如何将新项目插入到双向链表中？它们是插在头部还是尾部？或者在中间的任意位置？请注意，将项插入到双向链表的中间需要O（n），除非您维护指向单个项的指针，在这种情况下，维护这些额外的指针将需要时间。 – wookie919

这是我最喜欢的问题之一。在文献中，它被称为“在线列表标签”，或者只是“列表标签”。这里有一点在维基百科这里：https://en.wikipedia.org/wiki/Order-maintenance_problem#List-labeling

也许最实用的最简单的算法是您的目的是第一个在这里：https://www.cs.cmu.edu/~sleator/papers/maintaining-order.pdf。

它处理分摊的O（log N）时间的插入，并且要管理N个项目，您必须使用足够大的整数来存放N^2。几乎所有的实际情况都是64位整数。

来源

2016-12-06 03:24:59

非常感谢，这看起来很酷。这不应该是太难以impliment。 – Josiah

只是想为所有的.net开发者提供这个算法的nuget包管理器命令是：Install-Package C5 – Josiah

我最终选择的是自己的解决方案，因为它看起来像算法希望在插入下一个节点之前将整个列表存储在内存中。这并不好。

我的想法是借用算法的一些想法。我所做的就是让Ids整理并排序多长时间。那么这个算法很懒惰，可以在任何适合的地方填充条目。一旦它在某个小块的空间用完了，它会开始从丛中上下扫描，并尝试建立一个均匀的间距，以便如果扫描了n个项目，他们需要在它们之间共享n^2填充。

从理论上讲，这将意味着随着时间的推移，列表将被完美填充，并且鉴于我的ID是整数，我的排序顺序很长，永远不会出现无法实现n^2填充的场景。我无法说明操作次数的上限，但我的胆量告诉我，通过以1 /多项式频率进行多项式工作，我会做得很好。

来源

2017-01-29 06:54:41 Josiah

对链表进行简单排序

回答

相关问题