對鏈表進行簡單排序

我想創建一個帶有順序序列（整數屬性）的雙向鏈表，這樣按順序順序進行排序可以創建一個實際上等價於鏈接列表的數組。對鏈表進行簡單排序

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

對鏈表進行簡單排序

回答

相關問題