分布式與并行計(jì)算—并向算法實(shí)現(xiàn)
訪問【W(wǎng)RITE-BUG數(shù)字空間】_[內(nèi)附完整源碼和文檔]
原始串行快速排序算法中有“分而治之”的遞歸調(diào)用部分，在每次選擇pivoit并把序列按照小于pivoIt和大于pivoit分成兩類后，左右兩部分的遞歸排序可以并發(fā)執(zhí)行。
運(yùn)行時(shí)間
為了減小偶然性因素造成的時(shí)間差異，對(duì)每一個(gè)算法重復(fù)運(yùn)行10000次，取平均耗時(shí)。
考慮到“枚舉排序”所需時(shí)間（$O(n^2)$）遠(yuǎn)遠(yuǎn)長(zhǎng)于另外兩者，因此“枚舉排序”只運(yùn)行一遍。
時(shí)間（毫秒）快速排序枚舉排序歸并排序串行1.688922043.4941并行0.86042771.5046
并行算法實(shí)現(xiàn)
快速排序
原始串行快速排序算法中有“分而治之”的遞歸調(diào)用部分，在每次選擇pivoit并把序列按照
小于pivoIt和大于pivoit分成兩類后，左右兩部分的遞歸排序可以并發(fā)執(zhí)行，偽代碼如下。
ParallelQucikSort(data, p, r)
q = Partition(data, p, r) // partition會(huì)返回pivoit
task[1] = ParallelQuickSort(data, p, q - 1)
task[2] = ParallelQuickSort(data, q + 1, r)
? ?for j = 1 to 2 par-do
? ? task[i]
? ?return data
枚舉排序
枚舉排序原本會(huì)依次對(duì)每個(gè)元素進(jìn)行計(jì)數(shù)的操作，我們可以使這些操作并行化，偽代碼如下
ParallelEnumerateSort(data)
? ?sorted_data = new List
? ?for i = 1 to data.length par-do
? ? ? ?counter = 0
? ? ? ?for j = 1 to data.length do
? ? ? ? ? ?if data[j] < data[i]
? ? ? ? ? ? ? ?counter = counter + 1
? ? ? ?sorted_data[counter+1] = data[i]
? ?return sorted_data
歸并排序
歸并排序的并行化改進(jìn)與快速排序類似，都是在“分而治之”分完之后，對(duì)兩個(gè)子任務(wù)并行執(zhí)行，偽代碼如下
ParallelMergeSort(data)
? ?if (data.length==1)
? ? ? ?return data
? ?else
? ? ? ?new_data[1] = data[:data.length/2]
? ? ? ?new_data[2] = data[data.length/2:]
? ? ? ?for i = 1 to 2 par-do
? ? ? ? ? ?ParallelMergeSort(new_data[i])
? ? ? ?
? ? ? ?data = MergeData(new_data[1],new_data[2])
? ? ? ?return data
