并行計算中快速排序算法的改進

《并行計算中快速排序算法的改進》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、并行計算中快速排序算法的改進摘要：排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。排序是計算機科學(xué)中最重要的研究問題之一。本文先從串行的快速排序講起，進而過渡到并行的快速排序算法。串行算法的平均時間復(fù)雜為O(nlogn)，而并行算法的平均時間復(fù)雜度為O(2logn)，。但是當(dāng)數(shù)據(jù)量非常大的時候，傳統(tǒng)的快速排序辦法理論可行，但實際上卻是不可行的。為此，本文提出一種結(jié)合歸并排序的方法給出一種改進的并行快速排序，得到一個可以用在待排序的數(shù)據(jù)個數(shù)巨大時的實用的并行算法。關(guān)鍵

2、詞：快速排序；歸并排序；串行算法；并行算法；時間復(fù)雜度1.引言排序是計算機科學(xué)中最重要的研究問題之一。由于它的應(yīng)用廣泛和固有的理論上的重要性，2000年它被列為對科學(xué)和工程計算的研究與實踐影響最大的10大問題之一[1]。因此對于排序的研究既有理論上的重要意義，又有實際應(yīng)用價值。它在計算機圖形、計算機輔助設(shè)計、機器人、模式識別及統(tǒng)計學(xué)等領(lǐng)域具有廣泛應(yīng)用[2]。基本的排序問題是重排一個給定的數(shù)據(jù)項集，使它按遞增（或遞減）排列。數(shù)據(jù)項可以是具有線性順序的任意對象。例如，在典型商業(yè)數(shù)據(jù)處理應(yīng)用中數(shù)據(jù)項是記錄，每一個記

3、錄都包含有一個稱為關(guān)鍵字的特殊標(biāo)識符域，并且記錄是按關(guān)鍵字進行排序。排序能夠大大簡化查找或更新一個記錄的過程。到目前為止，盡管研究人員已經(jīng)設(shè)計了多種排序算法。但快速排序仍然是實際應(yīng)用中最常用的一種排序算法。對它復(fù)雜度的分析方法和數(shù)據(jù)結(jié)構(gòu)的研究是研究許多應(yīng)用問題的基礎(chǔ)?？焖倥判蛑惺褂玫姆种尾呗允窃O(shè)計有效計算幾何和組合問題算法的典型設(shè)計方法。本文將探討并行計算中快速排序的改進。2.快速排序簡介快速排序(Quicksort)［3］是對冒泡排序的一種改進。由C．A．R．Hoare在1962年提出。它的基本思想是:通過

4、一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列?？焖倥判蛩惴ㄊ抢梅种渭夹g(shù)的典型例子。分治策略分為三步。首先將問題分成若干大小基本相等的子問題；獨立地解決這些子問題；最后將子問題歸并成原問題的解。因此方法的有效性取決于對初始問題劃分的過程和最后一步歸并解的過程。假設(shè)待排序的n個元素存儲在數(shù)組A[0,n-1]中?？焖倥判蛩惴ǖ母呒壝枋鋈缦拢?1)從數(shù)組A[0,n-1

5、]中選取樞軸元素。(2)重排數(shù)組A中元素，并將其劃分成左右兩部分。使得數(shù)組中所有比樞軸元素小的元素在左部分中，比它大的元素在右部分中。(3)對左、右部分進行遞歸排序。如果先不看實現(xiàn)的細(xì)節(jié)和算法的正確性證明，不難看出算法使用了分治策略。在這種情況下，第一、二步相應(yīng)于劃分步，第三步求解歸約的子問題，實現(xiàn)對整個數(shù)組的排序，從而無需歸并步驟。在快速排序算法的描述中，忽視了兩個關(guān)鍵的問題：(1)選擇樞軸元素的方法；(2)如樞軸元素被選擇后，使用的劃分方法。6由于本文主要探討快速算法的并行化，故采用簡化的方法，直接選取數(shù)

6、組的首個元素為樞軸元素。1.歸并排序簡介歸并排序[4]（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（DivideandConquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。歸并排序具體工作原理如下(假設(shè)序列共有n個元素):(1)將序列每相鄰兩個數(shù)字進行歸并操作(merge)，形成floor(n/2)個序列，排序后每個序列包含兩個元素;(2)將上述序列再次歸并，

7、形成floor(n/4)個序列，每個序列包含四個元素;(3)重復(fù)步驟(2)，直到所有元素排序完畢。2.并行算法中的快速排序并行計算是實現(xiàn)高性能計算的主要技術(shù)手段[5]，排序問題是計算機科學(xué)中最重要的研究問題之一。對快速排序方法的研究表明，至今快速排序算法仍然是流傳久遠(yuǎn)的最實用的排序算法。盡管在最壞情況下，它的平均情況下的時間復(fù)雜度相當(dāng)好[6]。將串行的快速排序并行化，必然能夠提高對數(shù)據(jù)處理的效率。2.1PRAM－CRCW上快速排序算法執(zhí)行快排序可以看成是構(gòu)造一棵二叉樹，其中主元是根，小于等于主元的元素處于左子

8、樹，大于主元的元素處于右子樹。算法首先從選第一個主元開始，它劃分原序列為兩個自序列；然后相繼子序列中主元的選取則可并行執(zhí)行。當(dāng)這樣的二叉樹造好后，采用中序遍歷的方法就可得到一個有序序列[7]。令待排序的序列為(A1,…,An)，處理器Pi保存元素Ai，LC［1:n］和RC［1:n］分別記錄給定主元的左孩子和右孩子，fi中存有其元素是主元的處理器號。開始時所有處理器均將它們自己的處理器號寫入變量roo