是否有可能穩定排序O（n日誌n）與恆定輔助空間的數組？

鑑於Ñ元件的陣列，有一個排序算法，是否有可能穩定排序O（n日誌n）與恆定輔助空間的數組？

排序在至多爲O（n log n）的時間（並且可選地，O（n）的時間最好情況）
是穩定
需要O（1）若干輔助空間

鋁升排序算法我發現滿足只有兩個這些標準：

冒泡排序滿足2和3只
合併排序滿足1和2只
堆排序滿足1和3

是否有一個滿足所有三個標準的算法？

來源

2013-10-09 fuz

但是不可能以某種方式實現合併排序嗎？即使是陣列？ – gregor

由於遞歸，這是不可能的。當遞歸在遞歸樹下工作時，遞歸樹的高度最多爲log2（n）。該算法至多需要這麼大的空間來跟蹤遞歸所採用的分支。 –

@Kent存檔O（1）額外的空間（假設是一個跨平臺的機器模型）的確是可能的;請參閱堆排序和冒泡排序。 – fuz

來自：https://cstheory.stackexchange.com/

存在着帶O穩定就地排序算法（N log n）的比較和O（n）的移動。

參見：Gianni Franceschini：使用O（n log n）穩定地排序比較和O（n）移動。理論計算。 SYST。 40（4）：327-353（2007） http://www.springerlink.com/content/d7348168624070v7/

來源

2013-10-09 14:59:49

你能再給一些解釋嗎？根據常見問題解答，單純鏈接到資源是不夠的答案。此外，該算法是支付和不能訪問我。 – fuz

這是一個免費的源代碼，描述了一種技術，它試圖去除大的常量開銷，並且經常伴隨着O（1）額外的空間進行穩定的排序：http://comjnl.oxfordjournals.org/content/35/6/643.full。 PDF格式 –

是否有可能穩定排序O（n日誌n）與恆定輔助空間的數組？

回答

相關問題