排序d排序數組的算法

請幫忙瞭解下列算法的運行時間
我已經有d個已經排序的數組（每個數組有超過1個元素），總共有n個元素。
我想有大小的一個排序數組n
如果我沒有錯誤插入排序是在部分地排序的陣列線性運行
如果我將串聯此d陣列成一個n元件陣列，並用插入排序排序它
是不是一個部分排序的數組和排序在這個數組不會是O（n）？排序d排序數組的算法

來源

2013-02-25 MAB

插入排序對於小的N值是相當（相對）線性的。

我相信，如果N足夠大，那麼子陣列不會排序，這相當有幫助。

Timsor T是部分分類陣列

來源

2013-02-25 12:30:07

不是插入排序在部分排序的數組線性的時間？如果我連接這個數組不會部分排序？ – MAB 2013-02-25 12:34:21

是的，但在你的情況下，整個數組不是部分排序，只是「子」部分。換句話說，如果只有幾個條目不合適，那麼插入排序是正確的 - 但在您的情況下，您有部分已排序 - 但「整體」仍然相對未排序。 – 2013-02-25 12:36:33

我認爲這：http://www.sorting-algorithms.com/是非常有教育意義的（對我來說無論如何:-)） – 2013-02-25 12:37:18

不，這將需要二次的時間一個很好的候選人。如果每個元素距離它在一個排序數組中的位置最多有一個恆定的距離，那麼插入排序只是線性的，在這種情況下，它需要O（和）時間 - 這就是部分排序的含義。你沒有這個保證。

只有在子陣列的數量保證爲小常數的假設下，才能在線性時間內完成此操作。在這種情況下，您可以使用k-way merge。

來源

2013-02-25 12:30:53

什麼意思呢？ – MAB 2013-02-25 12:32:56

@MAB：沒關係，我犯了一個錯誤。請參閱最新的答案。 – 2013-02-25 12:38:26

插入排序爲O（n²），即使原始數組是串聯的幾個預分類數組。您可能需要使用mergesort將幾個已排序的數組合併到一個已排序的數組中。這會給你O（n·ln（d））性能

來源

2013-02-25 12:32:40

如果數組已知被排序，那麼將每個數組視爲一個隊列，排序「頭」，選擇最小的頭放入新的數組中，然後從數組中「彈出」選定的值。

如果D很小，那麼一個簡單的氣泡排序對於排序頭部效果很好，否則你應該使用某種插入排序，因爲只有一個元素需要放入順序中。

我相信這基本上是一個「合併排序」。當要排序的列表超出工作存儲空間時非常有用，因爲您可以先排序較小的列表，而不會發生顛簸，然後使用非常少的工作存儲進行組合。

來源

2013-02-25 12:35:26

排序d排序數組的算法

回答

相關問題