【導(dǎo)讀】行研究工作所取得的成果。除文中已注明引用的內(nèi)容外，本畢業(yè)設(shè)計（論文）不。包含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品成果。對本研究做出過重要貢。獻的個人和集體，均已在文中以明確方式標(biāo)明并表示了謝意。具有良好的可移植性，支持Fortran和C/C++編程語言，操作系統(tǒng)平。臺方面則支持UNIX系統(tǒng)以及Windows系統(tǒng)。OpenMP的重要性在于它能夠為。負載平衡和銷毀工作。而快速排序是對冒泡排序的一種改進，它采。用了分治的思想，是所有排序算法中最高效，應(yīng)用最廣泛的一種。OpenMP的快速排序算法進行分析并設(shè)計程序。細講解了它的優(yōu)缺點，闡述其發(fā)展趨勢。接著列舉了主要的幾個排序算法進行比。較說明，以便能更好地了解其性能特點。對快速排序算法分別從最好情況，最壞。最后對快速排序，基于歸并的快速排序，雙倍。快速排序舉例進行程序編碼，通過實踐編程來加深對本課題知識的掌握。

　　

【正文】 核心在于分割算法，也可以說是最有技巧的部分 。 在開始，我們要接觸高效排序算法了。實踐證明，快速排序是所有排序算法中最高效的一種。它采用了分治的思想：先保證列表的前半部分都小于后半部分，然后分別對前半部分和后半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是 它高效的原因。因為在排序算法中，算法的高效與否與列表中數(shù)字間的比較次數(shù)有直接的關(guān)系，而 保證列表的前半部分都小于后半部分 就使得前半部分的任何一個數(shù)從此以后都不再跟后半部分的數(shù)進行比較了，大大減少了數(shù)字間不必要的比較。 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計（論文） 22 快速 排序 （ Quicksort）是對 冒泡排序 的一種改進。由 C. A. R. Hoare在 1962年提出。它的基本思想是：通過一趟 排序 將要排序的 數(shù)據(jù)分割 成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部 分數(shù)據(jù)分別進行快速排序，整個排序過程可以 遞歸 進行，以此達到整個數(shù)據(jù)變成有序序列。 設(shè)要 排序 的 數(shù)組 是 A[0]……A[N 1]，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一趟快速 排序 。值得注意的是，快速 排序 不是一種穩(wěn)定的 排序算法 ，也就是說，多個相同的值的相對位置也許會在算法結(jié)束時產(chǎn)生變動。 一趟 快速 排序 的算法是： 1）設(shè)置兩個 變量 i、 j， 排序 開始的時候： i=0， j=N1； 2）以第一個 數(shù)組 元素作為關(guān)鍵數(shù)據(jù)，賦值給 key，即 key=A[0]； 3）從 j 開始向前搜索，即由后開始向前搜索（ j ），找到第一個小于 key的值 A[j]， A[i]與 A[j]交換； 4）從 i 開始向后搜索，即由前開始向后搜索（ i ++ ），找到第一個大于 key的 A[i]， A[i]與 A[j]交換； 5）重復(fù)第 5 步，直到 I=J； (3,4 步是在程序中沒找到時候 j=j1， i=i+1，直至找到為止。找到并交換的時候 i， j 指針位置不變。另外當(dāng) i=j 這過程一定正好是 i+或 j完成的最后令循環(huán)結(jié)束。） (6) test 圖 快排圖 示例 ：待排序的數(shù)組 A 的值分別是：（初始關(guān)鍵數(shù)據(jù)： key=49） 注意南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計（論文） 23 關(guān)鍵 key 永遠不變，永遠是和 key 進行比較，無論在什么位置，最后的目的就是把 key 放在中間，小的放前面大的放后面。 A[0] A[1] A[2] A[3] A[4] A[5] A[6] 49 38 65 97 76 13 27 進行第一次交換后： 27 38 65 97 76 13 49 ( 按照算法的第三步從后面開始找，此時 :J=6） 進行第二次交換后： 27 38 49 97 76 13 65 ( 按照算法的第四步從前面開始找 key 的值， 6549,兩者交換，此時：I=2 ) 進行第三次交換后： 27 38 13 97 76 49 65 ( 按照算法的第五步將又一次執(zhí)行算法的第三步從后開始找 進行第四次交換后： 27 38 13 49 76 97 65 ( 按照算法的第四步從前面開始找大于 key 的值， 9749，兩者交換，此時： I=3,J=5 ) 此時再執(zhí)行第三步的時候就發(fā)現(xiàn) I=J=3，從而結(jié)束一趟快速排序，那么經(jīng)過一趟快速排序之后的結(jié)果是： 27 38 13 49 76 97 65，即所有大于 key49的數(shù)全部在 49 的后面，所有小于 key（ 49）的數(shù)全部在 key（ 49）的前面。 值得一提的變種 快速排序算法 隨機化快排： 快速排序的最壞情況基于每次劃分對主元的選擇?；镜目焖倥判蜻x取第一個元素作為主元。這樣在數(shù)組已經(jīng)有序的情 況下，每次劃分將得到最壞的結(jié)果。一種比較常見的優(yōu)化方法是隨機化算法，即隨機選取一個元素作為主元。這種情況下雖然最壞情況仍然是 O(n^2），但最壞情況不再依賴于輸入數(shù)據(jù)，而是由于隨機函數(shù)取值不佳。實際上，隨機化快速排序得到理論最壞情況的可能性僅為 1/(2^n）。所以隨機化快速排序可以對于絕大多數(shù)輸入數(shù)據(jù)達到 O(nlogn）的期望時間復(fù)雜度。一位前輩做出了一個精辟的總結(jié)：“隨機化快速排序可以滿足一個人一輩子的人品需求。” 隨機化快速排序的唯一缺點在于，一旦輸入數(shù)據(jù)中有很多的相同數(shù)據(jù)，隨機化的效果將直接減弱。對于 極限情況，即對于 n個相同的數(shù)排序，隨機化快速排序的時間復(fù)雜度將毫無疑問的降低到 O(n^2）。解決方法是用一種方法進行掃描，使沒有交換的情況下主元保留在原位置。 平衡快排（ Balanced Quicksort）： 每次盡可能地選擇一個能夠代表中值的元南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計（論文） 24 素作為關(guān)鍵數(shù)據(jù)，然后遵循普通快排的原則進行比較、替換和遞歸。通常來說，選擇這個數(shù)據(jù)的方法是取開頭、結(jié)尾、中間 3個數(shù)據(jù)，通過比較選出其中的中值。取這 3個值的好處是在實際問題（例如信息學(xué)競賽??）中，出現(xiàn)近似順序數(shù)據(jù)或逆序數(shù)據(jù)的概率較大，此時中間數(shù)據(jù)必然成為中值，而也是 事實上的近似中值。萬一遇到正好中間大兩邊?。ɑ蚍粗┑臄?shù)據(jù)，取的值都接近最值，那么由于至少能將兩部分分開，實際效率也會有 2倍左右的增加，而且利于將數(shù)據(jù)略微打亂，破壞退化的結(jié)構(gòu)。 外部快排（ External Quicksort）： 與普通快排不同的是，關(guān)鍵數(shù)據(jù)是一段 buffer，首先將之前和之后的 M/2個元素讀入 buffer并對該 buffer中的這些元素進行排序，然后從被排序數(shù)組的開頭（或者結(jié)尾）讀入下一個元素，假如這個元素小于 buffer中最小的元素，把它寫到最開頭的空位上；假如這個元素大于 buffer中最大 的元素，則寫到最后的空位上；否則把 buffer中最大或者最小的元素寫入數(shù)組，并把這個元素放在 buffer里。保持最大值低于這些關(guān)鍵數(shù)據(jù)，最小值高于這些關(guān)鍵數(shù)據(jù)，從而避免對已經(jīng)有序的中間的數(shù)據(jù)進行重排。完成后，數(shù)組的中間空位必然空出，把這個 buffer寫入數(shù)組中間空位。然后遞歸地對外部更小的部分，循環(huán)地對其他部分進行排序。 三路基數(shù)快排 （ Threeway Radix Quicksort，也稱作 Multikey Quicksort、Multikey Quicksort）：結(jié)合了基數(shù)排序（ radix sort，如一般的字符串比較排序就是基數(shù)排序）和快排的特點，是字符串排序中比較高效的算法。該算法被排序數(shù)組的元素具有一個特點，即 multikey，如一個字符串，每個字母可以看作是一個key。算法每次在被排序數(shù)組中任意選擇一個元素作為關(guān)鍵數(shù)據(jù)，首先僅考慮這個元素的第一個 key（字母），然后把其他元素通過 key的比較分成小于、等于、大于關(guān)鍵數(shù)據(jù)的三個部分。然后遞歸地基于這一個 key位置對“小于”和“大于”部分進行排序，基于下一個 key對“等于”部分進行排序。 特性 空間效率 ： 由于快速排 序是遞歸的 ， 需要借助一個遞歸工作棧來保存每一層遞歸調(diào)用的必要信息 。[O㏒ 2(n+1)]。最壞的情況下 因為要進行 n1次遞歸調(diào)用 ， 所以棧的深度為 O(n)。 平均情況下 ， 棧的深度是 O㏒ 2(n)。 時間效率 ： 快速排序的運行時間與劃分是否對稱有關(guān)， 而后者又與具體使用的劃分算法有關(guān)?？焖倥判虻淖顗那闆r發(fā)生在兩個區(qū)域分別分別包含 n1個元素和 0個元素時 ，這種最大程度的不對稱性若發(fā)生在每一層遞歸上， 即對應(yīng)于初始排序表基本 有序或基于逆序排序時 ， 就得到最壞 情況下的時間復(fù)雜度是O(n2) 。 穩(wěn)定性 ： 在劃分算法中，若右端區(qū)間存在兩個關(guān)鍵字相同，且均小于基準(zhǔn)南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計（論文） 25 值的記錄，則在交換到左端區(qū)間后，她們的相對位置會發(fā)生變化， 即快速排序算法是一個不穩(wěn)定的排序方法 。 內(nèi)部排序 ： 快速排序是一種內(nèi)部排序方法。也就是說快速排序的排序?qū)ο笫亲x入內(nèi)存的數(shù)據(jù)。 原地排序 ： 在排序的具體操作過程中，除去程序運行實現(xiàn)的空間消費（例如遞歸棧），快速排序算法只需消耗確定數(shù)量的空間（即 S(1)，常數(shù)級空間）。 這個性質(zhì)的意義，在于在內(nèi)存空間受到限制的系統(tǒng)（例如 MCU）中， 速排序也能夠很 好地工作。 下面 就最好情況，最壞情況和平均情況對快速排序算法的性能作一點分析。 注意： 這里為方便起見，我們假設(shè)算法 Quick_Sort 的范圍閾值為 1（即一直將線性表分解到只剩一個元素），這對該 算法復(fù)雜性 的分析沒有本質(zhì)的影響。 我們先分析函數(shù) partition 的性能，該函數(shù)對于確定的輸入復(fù)雜性是確定的。觀察該函數(shù)，我們發(fā)現(xiàn)，對于有 n 個元素的確定輸入 L[p..r]，該函數(shù)運行時間顯然為 θ（ n）。 最壞情況 無論適用哪一種方法來選擇 pivot，由于我們不知道各個元素間的相對大小關(guān)系（若知道就已經(jīng)排好序了），所以我們無法確定 pivot的選擇對劃分造成的影響。因此對各種 pivot 選擇法 而言，最壞情況和最好情況都是相同的。 我們從直覺上可以判斷出最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個區(qū)間分別包含 n1 個元素和 1 個元素的時候（設(shè)輸入的表有 n 個元素）。下面我們暫時認為該猜測正確，在后文我們再詳細證明該猜測。 對于有 n 個元素的表 L[p..r]，由于函數(shù) Partition 的計算時間為 θ（ n），所以快速 排序 在序壞情況下的復(fù)雜性有 遞歸 式如下： T(1)=θ（ 1),T(n)=T(n1)+T(1)+θ（ n) (1) 用迭代法可以解出上式的解為 T(n)=θ（ n2）。 這個最壞情況運行時間與 插入排序 是一樣的。 下面我們來證明這種每次劃分過程產(chǎn)生的兩個區(qū)間分別包含 n1 個元素和 1 個元素的情況就是最壞情況。 設(shè) T(n）是過程 Quick_Sort 作用于規(guī)模為 n 的輸入上的最壞情況的時間，則 T(n)=max(T(q)+T(nq))+θ（ n)， 其中 1≤q≤n1 (2) 我們假設(shè)對于任何 kn，總有 T(k） ≤ck，其中 c 為常數(shù)；顯然當(dāng) k=1時是成立的。 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計（論文） 26 將歸納假設(shè)代入（ 2），得到： T(n） ≤max(cq2+c(nq)2)+θ（ n)=c*max(q2+(nq)2)+θ（ n) 因為在 [1,n1]上 q2+(nq)2 關(guān)于 q 遞減，所以當(dāng) q=1 時 q2+(nq)2 有最大值 n22(n1）。于是有： T(n） ≤22c(n1)+θ（ n） ≤2 只要 c 足夠大，上面的第二個小于等于號就可以成立。于是對于所有的 n 都有 T(n） ≤。 這樣，排序算法的最壞情況運行時間為 θ（ n2），且最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個區(qū)間分別包含 n1 個元素和 1 個元素的時候。 時間復(fù)雜度 為 o（ n2）。 最好情況 如果每次劃分過程產(chǎn)生的區(qū)間大小都為 n/2，則快速 排序 法運行就快得多了。這時有： T(n)=2T(n/2)+θ（ n),T(1)=θ（ 1) (3) 解得： T(n)=θ（ nlogn) 快速排序法最佳情況下執(zhí)行過程的遞歸樹如下圖所示，圖中 lgn 表示以2 位底的對數(shù)，而本文中用 logn 表示以 2 位底的對數(shù) . 由于快速排序法也是基于比較的排序法，其運行時間為 Ω（ nlogn)，所以如果每次劃分過程產(chǎn)生的區(qū)間大小都為 n/2，則運行時間 θ（ nlogn）就是最好情況運行時間。 但是，是否一定要每次平均劃分才能達到最好情況呢？要理解這一點就必須理解對稱性是如何在描述運行時間的遞歸式中反映的。我們假設(shè)每次劃分過程都產(chǎn)生 9:1 的劃分，乍一看該劃分很不對稱。我們可以得到遞歸式： T(n)=T(n/10)+T(9n/10)+θ（ n),T(1)=θ（ 1) (4) 請注意該樹的每一層都有代價 n，直到在深度 log10n=θ（ logn）處達到邊界條件，以后各層代價至多為 n。遞 歸于深度 log10/9n=θ（ logn）處結(jié)束。這樣，快速排序的總時間代價為 T(n)=θ（ nlogn），從漸進意義上看就和劃分是在中間進行的一樣。事實上，即使是 99:1 的劃分時間代價也為 θ（ nlogn）。其原因在于，任何一種按常數(shù)比例進行劃分所產(chǎn)生的遞歸樹的深度都為 θ（ nlogn），其中每一層的代價為 O(n），因而不管常數(shù)比例是什么，總的運行時間都為 θ（ nlogn），只不過其中隱含的常數(shù)因子有所不同。（關(guān)于 算法復(fù)雜性 的漸進階，請參閱 算法的復(fù)雜性 ) 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計（論文） 27 平均情況 我們首先對平均情況下的性能作直覺上的分析。 要想對快速 排序 的平均情況有個較為清楚的概念，我們就要對遇到的各種輸入作個假設(shè)。通常