哪種排序方法最適合並行處理？

我現在正在看我的舊學校作業，並希望找到問題的解決方案。哪種排序方法最適合並行處理？

哪種排序方法最適合並行處理？

我想快速排序（或歸併排序？）就是答案。

我正確嗎？

2009-11-23 Billy

像歸併排序，快速排序，也可以很容易地由於其分而治之的自然並行。單獨的就地分區操作難以並行化，但是一旦分割，列表的不同部分可以並行排序。

與其他並行排序算法相比，並行快速排序的一個優點是不需要同步。一旦一個子列表可用於其工作，並且它不與其他線程通信，就會啓動一個新線程。當所有線程完成時，排序完成。

2009-11-23 16:08:51

+1：一旦拆分，快速排序不需要同步。 Mergesort需要同步才能合併。 – 2009-11-23 19:00:23

「與其他並行排序算法相比，並行快速排序的一個優點是不需要同步」。呃，不。您顯然需要等待子任務完成才能返回答案，即同步。 – 2011-02-12 09:05:49

我認爲合併排序

你可以把數據集和他們進行並行操作..

2009-11-23 15:55:11 ufukgun

+1即使你的暱稱讓我害怕。 – Will 2009-11-23 16:03:28

我的名字是UfukGün，但在英文中它聽起來很有趣:) – ufukgun 2009-11-23 16:06:01

Mergesort需要線程之間的同步來合併排序結果。 Quicksort不需要任何線程同步。 – 2009-11-23 19:01:12

它完全依賴於並行化的方法。對於多線程通用計算，合併排序提供相當可靠的負載平衡和內存本地化屬性。對於硬件中的大型sorting network，如果要獲得良好的O（log²n）性能，則實際上最好使用Batcher，Bitonic或Shell排序形式。

2009-11-23 16:14:41

+1是唯一正確的答案。 – 2011-02-12 09:08:05

我認爲合併排序將是這裏最好的答案。因爲合併排序背後的基本思想是將問題分解成單個解決方案。解決它們併合並它們。

這就是我們在並行處理中所做的。將整個問題分成小單元語句並行計算，然後加入結果。謝謝

2012-03-26 19:21:12 mojito89

它是合併排序，因爲排序是在兩個子數組上完成的，並且它們在最後進行比較和排序。這些可以並行完成

2012-09-06 03:51:46 Nimmy

我不認爲有必要重複現有的答案。 – Mysticial 2012-09-22 21:45:15

回答