【正文】 通常都假設(shè)輸。（關(guān)于 算法復(fù)雜性 的漸進(jìn)階，請(qǐng)參閱 算法的復(fù)雜性 ) 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 27 平均情況 我們首先對(duì)平均情況下的性能作直覺上的分析。事實(shí)上，即使是 99:1 的劃分時(shí)間代價(jià)也為 θ（ nlogn）。遞 歸于深度 log10/9n=θ（ logn）處結(jié)束。我們假設(shè)每次劃分過程都產(chǎn)生 9:1 的劃分，乍一看該劃分很不對(duì)稱。這時(shí)有： T(n)=2T(n/2)+θ（ n),T(1)=θ（ 1) (3) 解得： T(n)=θ（ nlogn) 快速排序法最佳情況下執(zhí)行過程的遞歸樹如下圖所示，圖中 lgn 表示以2 位底的對(duì)數(shù)，而本文中用 logn 表示以 2 位底的對(duì)數(shù) . 由于快速排序法也是基于比較的排序法，其運(yùn)行時(shí)間為 Ω（ nlogn)，所以如果每次劃分過程產(chǎn)生的區(qū)間大小都為 n/2，則運(yùn)行時(shí)間 θ（ nlogn）就是最好情況運(yùn)行時(shí)間。 時(shí)間復(fù)雜度 為 o（ n2）。于是對(duì)于所有的 n 都有 T(n） ≤。 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 26 將歸納假設(shè)代入（ 2），得到： T(n） ≤max(cq2+c(nq)2)+θ（ n)=c*max(q2+(nq)2)+θ（ n) 因?yàn)樵?[1,n1]上 q2+(nq)2 關(guān)于 q 遞減，所以當(dāng) q=1 時(shí) q2+(nq)2 有最大值 n22(n1）。 下面我們來(lái)證明這種每次劃分過程產(chǎn)生的兩個(gè)區(qū)間分別包含 n1 個(gè)元素和 1 個(gè)元素的情況就是最壞情況。 對(duì)于有 n 個(gè)元素的表 L[p..r]，由于函數(shù) Partition 的計(jì)算時(shí)間為 θ（ n），所以快速 排序 在序壞情況下的復(fù)雜性有 遞歸 式如下： T(1)=θ（ 1),T(n)=T(n1)+T(1)+θ（ n) (1) 用迭代法可以解出上式的解為 T(n)=θ（ n2）。 我們從直覺上可以判斷出最壞情況發(fā)生在每次劃分過程產(chǎn)生的兩個(gè)區(qū)間分別包含 n1 個(gè)元素和 1 個(gè)元素的時(shí)候（設(shè)輸入的表有 n 個(gè)元素）。 最壞情況 無(wú)論適用哪一種方法來(lái)選擇 pivot，由于我們不知道各個(gè)元素間的相對(duì)大小關(guān)系（若知道就已經(jīng)排好序了），所以我們無(wú)法確定 pivot的選擇對(duì)劃分造成的影響。 我們先分析函數(shù) partition 的性能，該函數(shù)對(duì)于確定的輸入復(fù)雜性是確定的。 下面 就最好情況，最壞情況和平均情況對(duì)快速排序算法的性能作一點(diǎn)分析。 原地排序 ： 在排序的具體操作過程中，除去程序運(yùn)行實(shí)現(xiàn)的空間消費(fèi)（例如遞歸棧），快速排序算法只需消耗確定數(shù)量的空間（即 S(1)，常數(shù)級(jí)空間）。 內(nèi)部排序 ： 快速排序是一種內(nèi)部排序方法?？焖倥判虻淖顗那闆r發(fā)生在兩個(gè)區(qū)域分別分別包含 n1個(gè)元素和 0個(gè)元素時(shí) ，這種最大程度的不對(duì)稱性若發(fā)生在每一層遞歸上， 即對(duì)應(yīng)于初始排序表基本 有序或基于逆序排序時(shí) ， 就得到最壞 情況下的時(shí)間復(fù)雜度是O(n2) 。 平均情況下 ， 棧的深度是 O㏒ 2(n)。[O㏒ 2(n+1)]。然后遞歸地基于這一個(gè) key位置對(duì)“小于”和“大于”部分進(jìn)行排序，基于下一個(gè) key對(duì)“等于”部分進(jìn)行排序。該算法被排序數(shù)組的元素具有一個(gè)特點(diǎn)，即 multikey，如一個(gè)字符串，每個(gè)字母可以看作是一個(gè)key。然后遞歸地對(duì)外部更小的部分，循環(huán)地對(duì)其他部分進(jìn)行排序。保持最大值低于這些關(guān)鍵數(shù)據(jù)，最小值高于這些關(guān)鍵數(shù)據(jù)，從而避免對(duì)已經(jīng)有序的中間的數(shù)據(jù)進(jìn)行重排。萬(wàn)一遇到正好中間大兩邊?。ɑ蚍粗┑臄?shù)據(jù)，取的值都接近最值，那么由于至少能將兩部分分開，實(shí)際效率也會(huì)有 2倍左右的增加，而且利于將數(shù)據(jù)略微打亂，破壞退化的結(jié)構(gòu)。通常來(lái)說，選擇這個(gè)數(shù)據(jù)的方法是取開頭、結(jié)尾、中間 3個(gè)數(shù)據(jù)，通過比較選出其中的中值。解決方法是用一種方法進(jìn)行掃描，使沒有交換的情況下主元保留在原位置?！? 隨機(jī)化快速排序的唯一缺點(diǎn)在于，一旦輸入數(shù)據(jù)中有很多的相同數(shù)據(jù)，隨機(jī)化的效果將直接減弱。所以隨機(jī)化快速排序可以對(duì)于絕大多數(shù)輸入數(shù)據(jù)達(dá)到 O(nlogn）的期望時(shí)間復(fù)雜度。這種情況下雖然最壞情況仍然是 O(n^2），但最壞情況不再依賴于輸入數(shù)據(jù)，而是由于隨機(jī)函數(shù)取值不佳。這樣在數(shù)組已經(jīng)有序的情 況下，每次劃分將得到最壞的結(jié)果。 值得一提的變種 快速排序算法 隨機(jī)化快排： 快速排序的最壞情況基于每次劃分對(duì)主元的選擇。） (6) test 圖 快排圖 示例 ：待排序的數(shù)組 A 的值分別是：（初始關(guān)鍵數(shù)據(jù)： key=49） 注意南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 23 關(guān)鍵 key 永遠(yuǎn)不變，永遠(yuǎn)是和 key 進(jìn)行比較，無(wú)論在什么位置，最后的目的就是把 key 放在中間，小的放前面大的放后面。找到并交換的時(shí)候 i， j 指針位置不變。值得注意的是，快速 排序 不是一種穩(wěn)定的 排序算法 ，也就是說，多個(gè)相同的值的相對(duì)位置也許會(huì)在算法結(jié)束時(shí)產(chǎn)生變動(dòng)。它的基本思想是：通過一趟 排序 將要排序的 數(shù)據(jù)分割 成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部 分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以 遞歸 進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 22 快速 排序 （ Quicksort）是對(duì) 冒泡排序 的一種改進(jìn)。這是一種先進(jìn)的思想，也是 它高效的原因。實(shí)踐證明，快速排序是所有排序算法中最高效的一種。 快速排序的核心在于分割算法，也可以說是最有技巧的部分 。并把樞紐元素放在合適的位置。 九 快速排序 快速排序是目前使用可能最廣泛的排序算法 。對(duì)于如何安排每次落入同一個(gè)桶中的數(shù)據(jù)有兩種安排方法： 1）順序存儲(chǔ)：每次使用桶式排序，放入 r個(gè)桶中，相同時(shí)增加計(jì)數(shù)。 一般有兩種方式 : 1) 高位優(yōu)先 (MSD)： 從高位到低位依次對(duì)序列排序 2）低位優(yōu)先 (LSD)： 從低位到高位依次對(duì)序列排序 計(jì)算機(jī)一般采用低位優(yōu)先法（人類一般使 用高位優(yōu)先），但是采用低位優(yōu)先時(shí)要確保排序算法的穩(wěn)定性。而基數(shù)排序把每個(gè)排序碼拆成由 d個(gè)排序碼，比如任何一個(gè) 6位數(shù)（不滿六位前面補(bǔ) 0）拆成 6個(gè)排序碼，分別是個(gè)位的，十位的，百位的。 這里我們用兩個(gè)臨時(shí)性數(shù)組，一個(gè)用于記錄位置南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 21 信息，一個(gè)用于方便輸出數(shù)據(jù)成有序方式，另外我們假設(shè)數(shù)據(jù)落在 0到 MAX,如果所給數(shù)據(jù)不是從 0開始，你可以 把每個(gè)數(shù)減去最小的數(shù)。 桶式排序事先要知道待排序列在一個(gè)范圍內(nèi)，而且這個(gè)范圍應(yīng)該不是很大的。 顯然，堆排序也是一種選擇性的排序，每次選擇第 i大的元素。 堆主要有兩種核心操作， 1）從指定節(jié)點(diǎn)向上調(diào)整 (shiftUp) 2）從指定節(jié)點(diǎn)向下調(diào)整 (shiftDown) 建堆，以及刪除堆定節(jié)點(diǎn)使用 shiftDwon,而在插入節(jié)點(diǎn)時(shí)一般結(jié)合兩種操作一起使用。它的基本思想就是假設(shè)數(shù)組 A有 N個(gè)元素，那么可以看成數(shù)組 A是又 N個(gè)有序的子序列組成，每個(gè)子序列的長(zhǎng)度為 1，然后再兩兩合并，得到了一個(gè) N/2 個(gè)長(zhǎng)度為 2或 1的有序子序列，再兩兩合并，如此重復(fù)，直到得到一個(gè)長(zhǎng)度為 N的有序數(shù)據(jù)序列為止，這種排序方法稱為 2— 路合并排序。 這里每次分成若干小塊是通過“增量” 來(lái)控制的，開始時(shí)增量交大，接近N/2,從而使得分割出來(lái)接近 N/2個(gè)小塊，逐漸的減小“增量“最終到減小到 1。 這樣， n個(gè)記錄的文件的直接選擇排序可經(jīng)過 n1趟直接選擇排序得到有序結(jié)果。 ?? ③第 i趟排序 第 i趟排序開始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為 R[1..i1]和 R(1≤ i≤ n1)。 n個(gè)記錄的文件的直接選擇排序可經(jīng)過 n1趟直接選擇排序得到有序結(jié)果： ① 初始狀態(tài)：無(wú)序區(qū)為 R[1..n]，有序區(qū)為空。 9， 3， 5， 1， 6， 2， 8， 4， 7 3， 5， 1， 6， 2， 8， 4， 7， 9 南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 19 3， 1， 5， 2， 6， 4， 7， 8， 9 1， 3， 2， 5， 4， 6， 7， 8， 9 1， 2， 3， 4， 5， 6， 7， 8， 9 1， 2， 3， 4， 5， 6， 7， 8， 9 1， 2， 3， 4， 5， 6， 7， 8， 9 1， 2， 3， 4， 5， 6， 7， 8， 9 三 選擇排序 選擇排序的原理是 每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部 待排序的數(shù)據(jù)元素排完。重復(fù)以上過程，仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?2個(gè)數(shù)和第 3個(gè)數(shù)的交換，使得第 1個(gè)數(shù)不再小于第 2個(gè)數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到最大數(shù)前的一對(duì)相鄰數(shù)，將小數(shù)放前，大數(shù)放后，第二 趟結(jié)束，在倒數(shù)第二個(gè)數(shù)中得到一個(gè)新的最大數(shù)。即首先比較第 1個(gè)和第 2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。 直接插入排序?qū)儆诜€(wěn)定的排序，時(shí)間復(fù)雜性為 o(n^2)，空間復(fù)雜度為 O(1)。 第一趟比較前兩個(gè)數(shù) ,然后把第二個(gè)數(shù) 按大小插入到有序表中 。 比較 排序算法有多個(gè)不同的類型，接下來(lái)將舉出最主要的幾種算法，描述它們的特點(diǎn)進(jìn)行比較。作這件事情的一南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 18 個(gè)方式是人工擴(kuò)充鍵值的比較，如此在其他方面相同鍵值的兩個(gè)對(duì)象間之比較，就會(huì)被決定使用在原先數(shù)據(jù)次序中的條目，當(dāng)作一個(gè)同分決賽。 （ 4,1）（ 3,1）（ 3,7）（ 5,6）在這個(gè)狀況下，有可能產(chǎn)生兩種不同的結(jié)果，一個(gè)是依照相等的鍵值維持相對(duì)的次序，而另外一個(gè)則沒有： （ 3,1）（ 3,7）（ 4,1）（ 5,6） （維持次序 ) （ 3,7）（ 3,1）（ 4,1）（ 5,6） （次序被改變 ) 不穩(wěn)定排序算法可能會(huì)在相等的鍵值中改變紀(jì)錄的相對(duì)次序，但是穩(wěn)定排 序算法從來(lái)不會(huì)如此。 當(dāng)相等的元素是無(wú)法分辨的，比如像是整數(shù)，穩(wěn)定度并不是一個(gè)問題。基本上，排序算法的輸出必須遵守下列兩個(gè)原則： （遞增是針對(duì)所需的排序順序而言） 、或是重組 排序 (Sorting) 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)關(guān)鍵字有序的序列。有效的排序算法在一些算法（例如搜索算法與合并算法）中是重要的，如此這些算法才能得到正確解答。 與比較 在計(jì)算機(jī)科學(xué)與數(shù)學(xué)中，一個(gè)排序算法（ Sorting algorithm）是一種能將一串?dāng)?shù)據(jù)依照特定排序方式的一種算法。然后再對(duì)快速排序算法 進(jìn)行總體分析，以便能更好地了解其性能特點(diǎn)?？焖倥判虮粡V泛用作庫(kù)排序工具，而且還被應(yīng)用于其他意義重大的應(yīng)用中。其原因是它易于實(shí)現(xiàn)，能夠很好地適用于不同的輸入數(shù)據(jù)，而且在很多場(chǎng)合它的消耗的資源比其他任何排序的方法都少。通過簡(jiǎn)單的介紹，在復(fù)習(xí)編譯原理的基礎(chǔ)之上初步了解 OpenMP編譯所涉及的幾個(gè)問題，形成初步的概念。 簡(jiǎn)單分析了相應(yīng)的編譯器的基本構(gòu)件：詞法分析模塊、語(yǔ)法分析模塊、語(yǔ)義分析模塊、中間代碼生成、代碼優(yōu)化模塊、目標(biāo)代碼生成以及符號(hào)表管理和錯(cuò)誤檢查。由于編譯系統(tǒng)的各個(gè)部分都可能需要程序來(lái)診斷問題，所以錯(cuò)誤處理代碼是廣泛分布于編譯器的各個(gè)角落，在需要的地方進(jìn)行檢查和診斷并報(bào)告錯(cuò)誤所在 。在編譯過程中，造表和查表工作由一系列程序（或函數(shù)）來(lái)完成，它們并不是獨(dú)立的存在而是安插在編譯程序的相關(guān)功能代碼中。 由于 OpenMP并行語(yǔ)義是串行的 C語(yǔ)言中沒有的特性，因此需要在目標(biāo)代碼產(chǎn)生過程中進(jìn) 行翻譯變換，通過源代碼變換的同時(shí)結(jié)合底層的線程庫(kù)來(lái)實(shí)現(xiàn)OpenMP的并行語(yǔ)義，這是 OpenMP編譯的翻譯變換重點(diǎn)所在。 狹義的 OpenMP編譯只是源代碼級(jí)的變換，因此編譯原理課程中講述的目標(biāo)代碼生成技術(shù)并不完全適用。對(duì)框架代碼的要求做到：目標(biāo)代碼盡可能簡(jiǎn)潔、有較高的執(zhí)行效率。這個(gè)翻譯轉(zhuǎn)換過程，需要確定源語(yǔ)言的的各種語(yǔ)法成分（或中間代碼的各種結(jié)構(gòu)）對(duì)應(yīng)的目標(biāo)代碼結(jié)構(gòu)，該結(jié)構(gòu)稱為“框架”。但是對(duì)于運(yùn)行環(huán)境，其可優(yōu)化的地方就較多，例如對(duì)于 NUMA架構(gòu)的機(jī)器， OpenMP線程的數(shù)據(jù)分配以及線程對(duì)處理器核的綁定等等，都是當(dāng)前性能優(yōu)化的熱點(diǎn) 。對(duì)速度的優(yōu)化目標(biāo)可能會(huì)不利于存儲(chǔ)空間的優(yōu)化目標(biāo)，因此對(duì)各項(xiàng)優(yōu)化目標(biāo)應(yīng)當(dāng)進(jìn)行權(quán)衡。優(yōu)化工作可以分為與機(jī)器體系結(jié)構(gòu)相關(guān)的優(yōu)化和與機(jī)器體系結(jié)構(gòu)無(wú)關(guān)的優(yōu)化。 圖 代碼優(yōu)化程序 代碼優(yōu)化是為了提供更高質(zhì)量目標(biāo)代碼，該工作常常在中間代碼生成和目標(biāo)南京郵電大學(xué) 2020 屆本科生畢業(yè)設(shè)計(jì)（論文） 15 代碼輸出之 間插入一個(gè)代碼優(yōu)化處理的階段來(lái)實(shí)現(xiàn)。前端需要將源程序分解為多個(gè)獨(dú)立的組成要素，并在這些要素上重建語(yǔ)法結(jié)構(gòu)并輸出其中間表示，其間收集的有關(guān)信息需要存放到符號(hào)表中。 這種先將源程序翻譯為某種形式的中間代碼，然后再將其翻譯為目標(biāo)代碼的方法，可以使編譯程序前后兩部分功能更加單一，邏輯結(jié)構(gòu)更加清晰，從而使得編譯程序更易于編寫與調(diào)整，也為代碼優(yōu) 化和編譯器移植創(chuàng)造了條件。目前常見的中間代碼形式有逆波蘭表示、三元式、四元式以