2010-11-29 110 views
0

在「算法簡介」中,合併排序算法使用名爲MERGE(A, p, q, r)的幫助程序函數實現 - 即合併兩個先前排序的序列。合併排序:是否需要額外的陣列副本?

該功能引入了兩個附加陣列LR

MERGE(A, p, q, r) 
1 n1 ← q − p + 1 
2 n2 ←r − q 
3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1] 
..... 

"create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]"我知道爲他們分配額外的內存。

是否可以重寫這個函數,以便我不需要額外的內存,並直接操作到A?

回答

2

當然。它被稱爲就地合併排序。

Wikipedia說這是複雜的 - 但它並不總是如此。 Some不像others那麼複雜,如果你don't care about the run-time

有幾個方差,有些是穩定的,有些是不穩定的。例如,請參閱NIST DIAGS下的「實施」部分。

+0

另請參閱此問題:http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm – 2010-11-29 14:59:21

1

是的,這就是所謂的就地合併排序,但Wikipedia所言:

排序就地是可能的(例如,使用列表而不是數組),但非常複雜,並會提供小即使算法在O(n log n)時間內運行,在實踐中性能也會有所提高。 (Katajainen,Pasanen & Teuhola 1996)