C語(yǔ)言與程序設(shè)計(jì)ppt-第13章

C語(yǔ)言與程序設(shè)計(jì)

TheCandProgramming

第13章排序

華中科技大學(xué)計(jì)算機(jī)學(xué)院

2/5/20231華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組本章講授內(nèi)容

排序是數(shù)據(jù)處理領(lǐng)域一種基本且常用的算法。排序的目的之一是便于檢索。算法設(shè)計(jì)的好壞直接影響計(jì)算機(jī)的運(yùn)行時(shí)間，計(jì)算機(jī)排序方法較多，時(shí)間復(fù)雜度差別較大。本章介紹直接插入排序；shell排序；歸并排序；算法的時(shí)間復(fù)雜度；排序算法的應(yīng)用實(shí)例。

2/5/20232華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組13.1直接插入排序直接插入排序的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當(dāng)位置，直到全部記錄插入為止。具體過(guò)程為：假設(shè)待排序的n個(gè)記錄存放在數(shù)組a中，a被劃分成兩個(gè)子區(qū)：有序區(qū)(a[0]～a[i-1])和無(wú)序區(qū)(a[i]～a[n-1])。開始時(shí)，i=1，即有序區(qū)中只包含1個(gè)元素a[0]，無(wú)序區(qū)中包含有n-1個(gè)元素(a[1]～a[n-1])。排序過(guò)程中每次從無(wú)序區(qū)中取出第1個(gè)元素a[i]，將它插入到有序區(qū)中的適當(dāng)位置，使a[0]～a[i]成為新的有序區(qū)，重復(fù)n-1次可完成排序過(guò)程。因?yàn)檫@種方法每次使有序區(qū)增加1個(gè)記錄，通常稱增量法。2/5/20233華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組直接插入排序的過(guò)程圖13.1給出a={25,10,45,75,15}時(shí)的直接插入排序過(guò)程，其中大括號(hào)內(nèi)為有序區(qū)，后面為無(wú)序區(qū)。第1趟i=1: {25} 10 45 75 15 {10 25} 45 75 15第2趟i=2: {10 25} 45 75 15 {10 25 45} 75 15第3趟i=3: {10 25 45} 75 15 {10 25 45 75} 15第4趟i=4: {10 25 45 75} 15 {10 15 25 45 75}

圖13.1直接插入排序的過(guò)程2/5/20234華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組【例13.1】編程實(shí)現(xiàn)直接插入排序算法要求計(jì)算機(jī)生成若干個(gè)3位的隨機(jī)整數(shù)，放入數(shù)組，完成對(duì)數(shù)組的升序排序。分析：本實(shí)例要完成兩個(gè)功能：①產(chǎn)生隨機(jī)數(shù)放入數(shù)組；②對(duì)數(shù)組排序。按照結(jié)構(gòu)化程序設(shè)計(jì)思想，分別定義函數(shù)CreateData和InsertSort實(shí)現(xiàn)這兩個(gè)功能,然后編寫主函數(shù)main對(duì)程序功能進(jìn)行測(cè)試，輸出排序結(jié)果。2/5/20235華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組函數(shù)CreateData由于需要產(chǎn)生在兩個(gè)極限值之間取值的數(shù)據(jù)，為了使函數(shù)CreateData有通用性，函數(shù)原型為：

voidCreateData(inta[],intn,intlow,inthigh)；其功能是產(chǎn)生n個(gè)low～high之間的隨機(jī)整數(shù)放入數(shù)組a中。這樣模擬100個(gè)考試成績(jī)數(shù)據(jù)，可以調(diào)用CreateData(a，100，0,100)。2/5/20236華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組產(chǎn)生限定范圍隨機(jī)數(shù)的方法調(diào)用rand庫(kù)函數(shù)產(chǎn)生的隨機(jī)數(shù)在0到RAND_MAX之間，需要將其轉(zhuǎn)換到一個(gè)更有限的范圍，可以運(yùn)用以下四個(gè)步驟：（1）將rand庫(kù)函數(shù)產(chǎn)生的值限制為一個(gè)浮點(diǎn)數(shù)d，范圍是0≤d<1。（2）用乘法將d的值按照需要的范圍擴(kuò)大若干倍；（3）將上述值的小數(shù)部分截去，即產(chǎn)生以0為最小值的一定范圍的隨機(jī)整數(shù)；（4）修改數(shù)值的范圍使得從需要的最小值開始。2/5/20237華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組函數(shù)InsertSortInsertSort實(shí)現(xiàn)對(duì)n個(gè)整數(shù)的直接插入排序，原型為：

voidInsertSort(inta[],intn)；直接插入排序算法步驟：（1）初始時(shí)，a[0]自成1個(gè)有序區(qū)，無(wú)序區(qū)為a[1]～a[n-1]，令i=1；（2）將a[i]插入到有序區(qū)，過(guò)程如下：Ⅰ.使用變量temp臨時(shí)保存待插入元素a[i]；Ⅱ.從有序區(qū)尾部開始，查找應(yīng)插入的位置，若有序區(qū)中的元素大于待插入元素，則將其后移一個(gè)位置，繼續(xù)查找，否則，查找過(guò)程結(jié)束；Ⅲ.已經(jīng)騰出的位置即為插入位置，將待插入元素temp直接插入此位置，形成a[0]～a[i]的有序區(qū)。（3）i++，轉(zhuǎn)（2）直到i≥n。2/5/20238華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組程序\源程序\ex13_1.c程序的內(nèi)循環(huán)是實(shí)現(xiàn)從后往前查找應(yīng)插入位置，在查找中，為防止數(shù)組越界，要判斷j>=0。2/5/20239華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組直接插入排序算法的改進(jìn)為了進(jìn)一步提高直接插入排序的效率，可以引入被稱為哨兵的附加元素a[0],被排序的記錄放在a[1]～a[n-1]中。哨兵a[0]有兩個(gè)作用：①暫時(shí)存放待插入的元素；②防止數(shù)組下標(biāo)越界，一旦越界（即j=0），因?yàn)楹妥约罕容^，循環(huán)判定條件不成立使得查找循環(huán)結(jié)束,不會(huì)出現(xiàn)越界（for循環(huán)無(wú)需判斷j>=0，提高了效率）。實(shí)際上，一切為簡(jiǎn)化邊界條件而引入的附加結(jié)點(diǎn)（元素）稱為哨兵。引入哨兵后使得測(cè)試查找循環(huán)條件的時(shí)間大約減少了一半，當(dāng)記錄數(shù)較大時(shí)節(jié)約的時(shí)間是相當(dāng)可觀的。所以，不能把算法中的哨兵視為雕蟲小技，而應(yīng)該深刻理解并掌握這種技巧。通過(guò)將折半法應(yīng)用于查找應(yīng)插入的位置，可以減少關(guān)鍵字的比較次數(shù)，改善算法的性能。2/5/202310華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組13.2Shell排序在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)元素，并且對(duì)插入下一個(gè)數(shù)沒(méi)有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過(guò)多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.shell于1959年實(shí)現(xiàn)了這一思想。希爾排序的基本思想是：先將要排序的n個(gè)數(shù)按間隔gap（gap<n）分成若干組，每組中元素的下標(biāo)相差gap。對(duì)每組中全部元素進(jìn)行直接插入法排序，然后再用一個(gè)較小的間隔重復(fù)上述分組和排序，直至間隔為1，即所有元素放在一組中進(jìn)行直接插入排序?yàn)橹?。由于每次增量不斷縮小，該算法又稱為縮小增量排序算法。2/5/202311華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組Shell排序的過(guò)程間隔的選擇是希爾排序的重要部分，只要最終間隔為1，任何間隔序列都可以。Shell本人最初提出取初始gap=n/2，以后每次減小一倍，即gap=gap/2。下圖是16個(gè)數(shù)的Shell排序過(guò)程。2/5/202312華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組Shell排序算法步驟（1）初始時(shí)，間隔gap=n/2，即所有間隔為gap的記錄分成一組；（2）從第1組的第2個(gè)元素開始，即置循環(huán)變量i=gap，順序掃描整個(gè)待排序記錄，對(duì)每個(gè)元素a[i]分別在各組中進(jìn)行插入排序；Ⅰ.使用變量t臨時(shí)保存待插入元素a[i]；Ⅱ.在組內(nèi)從后往前查找應(yīng)插入的位置。具體方法是，置循環(huán)變量j=i-gap，將待插入元素t與a[j]進(jìn)行比較，若a[j]>t，則將a[j]在組內(nèi)后移一個(gè)位置，然后，j-=gap，繼續(xù)與組內(nèi)的前一個(gè)元素進(jìn)行比較；直至a[j]<=a[i]或者數(shù)組越界；Ⅲ.將待插入元素t插入相應(yīng)位置；Ⅳ.i++，轉(zhuǎn)（2）-Ⅰ直到處理完最后一個(gè)記錄。（3）間隔縮小一半，即gap/=2，轉(zhuǎn)（2），直到比較間隔縮小到0。2/5/202313華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組【例13.2】編程實(shí)現(xiàn)Shell排序算法要求計(jì)算機(jī)生成若干個(gè)0～100的整數(shù)，放入數(shù)組，完成對(duì)數(shù)組的升序排序。分析：定義函數(shù)ShellSort實(shí)現(xiàn)Shell排序算法,然后編寫主函數(shù)main進(jìn)行測(cè)試，輸出排序結(jié)果。\源程序\ex13_2.c函數(shù)ShellSort使用了三重for循環(huán)，最外層循環(huán)用來(lái)控制組內(nèi)元素的間隔gap，從n/2開始，以后減半，直至為1。中間循環(huán)用于控制每一個(gè)元素，按設(shè)置的間距gap，對(duì)每一組元素排序。最內(nèi)層循環(huán)使用插入排序法對(duì)一組指定間距的元素進(jìn)行排序。2/5/202314華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組13.3歸并排序歸并（merge）就是將兩個(gè)或多個(gè)有序的數(shù)列合成一個(gè)有序的數(shù)列。若將兩個(gè)有序的數(shù)列合成一個(gè)有序的數(shù)列則稱為二路歸并，若將三個(gè)有序的數(shù)列合成一個(gè)有序的數(shù)列則稱為三路歸并，同理，還有四路等多路歸并。歸并排序是建立在歸并操作上的一種有效的排序算法。2/5/202315華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組二路歸并排序二路歸并排序最簡(jiǎn)單，其基本思想是：將待排序序列a[0]到a[n-1]看成n個(gè)長(zhǎng)度為1的有序子序列，把這些子序列兩兩歸并，便得到(n/2)個(gè)長(zhǎng)度為2（最后一個(gè)序列的長(zhǎng)度可能小于2）的有序子序列，稱此為一趟歸并排序；然后再把這(n/2)個(gè)有序的子序列兩兩歸并，如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為n的有序序列。例如,有7個(gè)元素的數(shù)組{15，200，105，280，30，9，5}，要進(jìn)行3趟歸并，其排序過(guò)程如圖13.3所示。2/5/202316華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組歸并排序的過(guò)程例如,有7個(gè)元素的數(shù)組

{15，200，105，280，30，9，5}，要進(jìn)行3趟歸并，其排序過(guò)程如下所示。2/5/202317華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組函數(shù)merge在歸并排序過(guò)程中，要反復(fù)執(zhí)行數(shù)組中相鄰兩個(gè)有序序列的歸并操作。用函數(shù)merge實(shí)現(xiàn)該歸并算法。假設(shè)待歸并的兩個(gè)有序序列分別存于數(shù)組a中從下標(biāo)low到下標(biāo)mid的單元和從下標(biāo)mid+1到下標(biāo)high的單元，結(jié)果放到數(shù)組b中從下標(biāo)low到下標(biāo)high的單元。歸并過(guò)程為：①設(shè)定3個(gè)索引i=low，j=mid+1，k=low，最初位置分別為3個(gè)有序序列的起始位置。②比較a[i]和a[j]的大小，選擇相對(duì)小的元素復(fù)制給b[k]。a[i]<=a[j],則將第1個(gè)有序序列中的元素a[i]復(fù)制給b[k]，i和k再分別加1，即移動(dòng)索引到下一位置；否則，將第2個(gè)有序序列中的元素a[j]復(fù)制給b[k]，j和k再分別加1。③重復(fù)步驟②直到索引i或j達(dá)到序列尾，即某個(gè)有序序列的元素全部比較和復(fù)制完。④將另一序列剩下的所有元素直接復(fù)制給b。2/5/202318華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組函數(shù)MergePass在歸并算法的基礎(chǔ)上，再給出一趟歸并排序的算法，用函數(shù)MergePass實(shí)現(xiàn),它需要多次調(diào)用歸并算法。設(shè)數(shù)組a[0]～a[n-1]中每個(gè)有序序列的長(zhǎng)度為len（但最后一個(gè)序列的長(zhǎng)度可能小于len），進(jìn)行兩兩歸并后的結(jié)果放到數(shù)組b[0]～b[n-1]中。一趟歸并排序的過(guò)程為：①設(shè)定索引start，指向每一對(duì)待合并有序序列的開始位置，初值為0。②對(duì)數(shù)組a中從索引start開始的兩個(gè)長(zhǎng)度為len的有序序列，調(diào)用merge(a,b,start,start+len-1,start+len*2-1)完成歸并，然后start加2*len，即移動(dòng)索引到下一對(duì)待合并有序序列的開始位置。③轉(zhuǎn)步驟②直到索引start開始的有序表中有一個(gè)的長(zhǎng)度小于len④如果還剩下兩個(gè)不等長(zhǎng)的有序序列，則調(diào)用merge(a,b,start,start+len-1,n-1)對(duì)其完成歸并。⑤如果還剩下最后一個(gè)有序序列，則把它直接復(fù)制到b中即可。2/5/202319華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組函數(shù)MergeSort歸并排序就是反復(fù)調(diào)用一趟歸并排序算法MergePass，第一趟len=1，以后每進(jìn)行一趟len加倍。設(shè)待排序的n個(gè)數(shù)保存在數(shù)組a中，歸并過(guò)程中使用輔助數(shù)組temp，第一趟由a歸并到temp，第二趟由temp歸并到a，如此反復(fù)，直到n個(gè)數(shù)據(jù)成為一個(gè)有序序列。在歸并過(guò)程中，為了將最后的排序結(jié)果仍放于a中，需要進(jìn)行偶數(shù)趟，如果實(shí)際只需奇數(shù)趟，那么最后還要進(jìn)行一趟，此時(shí)temp中只有一個(gè)有序序列，它會(huì)被直接復(fù)制到a中。2/5/202320華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組【例13.3】用歸并排序法對(duì)n個(gè)整型數(shù)進(jìn)行升序排序。\源程序\ex13_3.c2/5/202321華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組13.4時(shí)間復(fù)雜度同一問(wèn)題可用不同算法解決，而一個(gè)算法的質(zhì)量?jī)?yōu)劣將影響到算法乃至程序的效率。通常用時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量算法效率。時(shí)間復(fù)雜度是度量算法執(zhí)行的時(shí)間長(zhǎng)短；而空間復(fù)雜度是度量算法所需存儲(chǔ)空間的大小。對(duì)于排序問(wèn)題，如果待處理的數(shù)據(jù)量巨大，就應(yīng)該認(rèn)真分析各種排序法的時(shí)間復(fù)雜度，從中選出運(yùn)行效率最高的方法。2/5/202322華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組1、時(shí)間復(fù)雜度的測(cè)試【例13.4】按如下步驟編制程序測(cè)試算法的時(shí)間復(fù)雜度：（1）隨機(jī)產(chǎn)生N個(gè)取值在0～20000之間的整數(shù)存入數(shù)組a；（2）分別采用直接插入排序、Shell排序和歸并排序3種算法對(duì)數(shù)組a作升序排列；（3）對(duì)每種算法實(shí)現(xiàn)，調(diào)用函數(shù)ftime記錄從算法開始運(yùn)行到運(yùn)行結(jié)束的時(shí)間。試比較三種排序算法的時(shí)間復(fù)雜度。從測(cè)試結(jié)果看出，當(dāng)數(shù)據(jù)量較小時(shí)，3種排序算法相差不大，但是，當(dāng)數(shù)據(jù)量增大時(shí)，希爾排序和歸并排序顯示出了明顯的優(yōu)勢(shì)。因此，當(dāng)待排序數(shù)據(jù)n較大時(shí)，宜采用Shell、歸并排序等時(shí)間復(fù)雜度小的算法。2/5/202323華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組2、時(shí)間復(fù)雜度的計(jì)算雖然一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間可以上機(jī)運(yùn)行測(cè)試得到，但是，評(píng)價(jià)一個(gè)算法的時(shí)間性能沒(méi)有必要都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。算法的實(shí)際運(yùn)行時(shí)間因機(jī)器而異，它取決于算法中的語(yǔ)句執(zhí)行次數(shù)和每條語(yǔ)句執(zhí)行的時(shí)間，由于每條語(yǔ)句執(zhí)行的時(shí)間取決于計(jì)算機(jī)，與算法的好壞無(wú)關(guān)，所以用算法中的語(yǔ)句執(zhí)行次數(shù)來(lái)表示算法的時(shí)間復(fù)雜度。2/5/202324華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組漸進(jìn)時(shí)間復(fù)雜度如果一個(gè)問(wèn)題的規(guī)模是n，解決這一問(wèn)題的算法中的語(yǔ)句執(zhí)行次數(shù)是n的一個(gè)函數(shù)，記為T(n)，當(dāng)n很大時(shí)，精確計(jì)算T(n)是很難而且也是沒(méi)有必要的。對(duì)于算法時(shí)間性能的分析并不需要得到T(n)的精確值，它的變化趨勢(shì)和規(guī)律也能清楚地反映算法的時(shí)間消耗。為此，引入漸進(jìn)時(shí)間復(fù)雜度，就是時(shí)間復(fù)雜度的極限情形，用大O表示法O(f(n))表示，O表示數(shù)量級(jí)，其中，f(n)就是T(n)的最高階。2/5/202325華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組冒泡排序的時(shí)間復(fù)雜度分析冒泡排序算法的核心代碼為：for(i=0;i<n-1;i++)for(j=0;j<n-1-i;j++)if(a[j+1]<a[j])swap(a[j],a[j+1]);該段代碼的基本操作是比較，因?yàn)楸容^是每次都要做的，而交換不一定每次都要做，T(n)的值就是一共要進(jìn)行的比較次數(shù)（即if語(yǔ)句的執(zhí)行次數(shù)）。最內(nèi)層循環(huán)的次數(shù)是(n-i-1)，外層循環(huán)i從0到n-2，所以總數(shù)是對(duì)(n-1-i)求和，其中i從0到n-2，即T(n)=(n-1)+(n-2)+…+1=n(n-1)/2。最高階是n2冒泡排序算法的時(shí)間復(fù)雜度是O(n2)，它表明：隨著n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和n2的增長(zhǎng)率成正比。2/5/202326華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組二分查找的時(shí)間復(fù)雜度分析二分查找的基本思想和下面代碼是一致的：while(n>=1){n/=2;}其時(shí)間復(fù)雜度就是while循環(huán)的次數(shù)，令循環(huán)次數(shù)為k，則有n/2k>=1，即2k<=n，k<=log2n，取最大值k=log2n，二分法的時(shí)間復(fù)雜度是O(log2n)。2/5/202327華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組常見的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列，常見的時(shí)間復(fù)雜度有：常數(shù)階O(1)、對(duì)數(shù)階、線性階O(n)、線性對(duì)數(shù)階、平方階O(n2)、立方階O(n3)、…、k次方階O(nk)、指數(shù)階O(2n)和階乘階O(n！)。隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。2/5/202328華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組直接插入排序的時(shí)間復(fù)雜度排序中的兩個(gè)基本操作是比較和移動(dòng)，因此排序的時(shí)間性能取決于排序過(guò)程中這兩個(gè)操作的次數(shù)。對(duì)于直接插入排序算法，這兩個(gè)操作的次數(shù)取決于待排數(shù)據(jù)序列的狀態(tài)。首先外層循環(huán)要進(jìn)行n-1次插入，每次插入最少比較1次，移動(dòng)2次（正序）；最多比較i次，移動(dòng)i+2次（逆序）（i=1，2，…，n-1）。因此，直接插入排序在最好和最壞情況下時(shí)間復(fù)雜度分別為O(n)和O(n2)。若待排記錄序列處于隨機(jī)狀態(tài)，則以最壞和最好情況的平均值作為插入排序的時(shí)間性能的量度，時(shí)間復(fù)雜度為O(n2)。直接插入法時(shí)間復(fù)雜度雖然也為O(n2)，但是它比冒泡排序的性能要好一些。2/5/202329華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組shell排序的時(shí)間復(fù)雜度Shell排序的時(shí)間復(fù)雜度分析比較復(fù)雜，例13.2的算法是三重循環(huán),外循環(huán)為log2n數(shù)量級(jí),中間循環(huán)為n數(shù)量級(jí),內(nèi)循環(huán)遠(yuǎn)遠(yuǎn)低于n數(shù)量級(jí),因?yàn)楫?dāng)開始分組較多時(shí)，每組的元素少，循環(huán)次數(shù)就少，后來(lái)增量逐漸縮小，分組數(shù)也逐漸減少，各組的元素逐漸增多，但由于元素逐漸接近于有序狀態(tài)，所以循環(huán)次數(shù)不會(huì)隨之增加。Shell排序算法的時(shí)間復(fù)雜度介于和O(n2)，約為O（n1.3）2/5/202330華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組歸并排序的時(shí)間復(fù)雜度歸并排序要進(jìn)行(log2n)趟歸并，每趟歸并的時(shí)間復(fù)雜度為O(n)。所以，歸并排序算法的時(shí)間復(fù)雜度為O(nlog2n)。但是，歸并排序占有附加存儲(chǔ)較多，需要另外一個(gè)與原排序數(shù)組同樣大小的輔助數(shù)組，其空間復(fù)雜度為O(n)，這是該算法的不足。2/5/202331華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組【例13.5】試設(shè)計(jì)一時(shí)間復(fù)雜度為O(n)的高效排序算法，高考成績(jī)排序。設(shè)數(shù)組a中存有100萬(wàn)高考學(xué)生的數(shù)學(xué)成績(jī)，且每個(gè)分?jǐn)?shù)為0到150之間的整數(shù)值。分析：已經(jīng)介紹的插入、快速、歸并等排序算法都是基于比較的，時(shí)間復(fù)雜度至少為O(nlog2n)，所以前述的各種排序法都滿足不了要求。2/5/202332華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組計(jì)數(shù)排序法由于要排序數(shù)組元素的值都在0到150的小范圍內(nèi)，因此創(chuàng)建一個(gè)長(zhǎng)度為151的數(shù)組buf，buf中每個(gè)元素記錄要排序數(shù)組中對(duì)應(yīng)分?jǐn)?shù)的出現(xiàn)個(gè)數(shù)，比如，a中90分有2個(gè)，則buf[90]的值為2。假設(shè)要排序的數(shù)組為a={1,0,3,1,0,1,1}，最大值為3，最小值為0，首先創(chuàng)建一個(gè)長(zhǎng)度為4的數(shù)組buf。然后一趟掃描數(shù)組a，得到a中各個(gè)元素出現(xiàn)的數(shù)目保存到數(shù)組buf的對(duì)應(yīng)單元中。一趟掃描完數(shù)組a后，buf={2，4，0，1}。從buf的值可知：a中有2個(gè)0，3個(gè)1，1個(gè)3。最后把buf中的記錄按每個(gè)元素的計(jì)數(shù)展開到數(shù)組a中，排序就完成了。也就是a[0]到a[1]為0，a[2]到a[5]為1……依此類推。\源程序\ex13_5.c2/5/202333華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組計(jì)數(shù)排序法分析計(jì)數(shù)排序法依靠一個(gè)輔助數(shù)組來(lái)實(shí)現(xiàn)，不基于比較，只需要對(duì)待排序數(shù)組掃描一遍，所以，算法復(fù)雜度為O(n)，利用空間換取了時(shí)間，就是多占用內(nèi)存，加快運(yùn)行速度。這種算法不適合范圍很大的數(shù)的排序。2/5/202334華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組13.5排序程序設(shè)計(jì)13.5.1多關(guān)鍵字的排序多關(guān)鍵字排序有一定的使用范圍，例如，在對(duì)高考分?jǐn)?shù)處理時(shí)，除了需對(duì)總分進(jìn)行排序外，不同的專業(yè)對(duì)單科分?jǐn)?shù)的要求不同，因此在總分相同的情況下，按用戶提出的單科分?jǐn)?shù)的次序要求排出考生錄取的次序。2/5/202335華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組【例13.6】奧運(yùn)獎(jiǎng)牌的排名編寫程序?qū)崿F(xiàn)奧運(yùn)會(huì)獎(jiǎng)牌不同要求的排名：首先按奧運(yùn)金牌總數(shù)排名，當(dāng)金牌總數(shù)相同時(shí)，按銀牌總數(shù)排名，當(dāng)銀牌總數(shù)也相同時(shí)，按銅牌總數(shù)排名，如果三種獎(jiǎng)牌數(shù)據(jù)都相同，按國(guó)家名稱的字典順序排序。奧運(yùn)獎(jiǎng)牌的排名為按多關(guān)鍵字的排名。按要求的關(guān)鍵字次序?qū)蓚€(gè)國(guó)家的記錄進(jìn)行比較由函數(shù)cmp完成，先比較金牌數(shù)，金牌不同時(shí)函數(shù)返回非零值，否則，比較銀牌數(shù)，銀牌不同時(shí)函數(shù)返回非零值，否則，比較銅牌數(shù)，不同時(shí)函數(shù)返回非零值，最后比較國(guó)家名稱。2/5/202336華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組函數(shù)ShellSort排序由函數(shù)ShellSort完成，用希爾排序法將指針x指向的n個(gè)元素排序，size是各元素的占用空間字節(jié)數(shù)，fcmp是指向函數(shù)的指針，用于確定排序的順序。因此，該函數(shù)對(duì)于排序有更好的兼容性，可以對(duì)任何數(shù)據(jù)類型，采取個(gè)人需要的排序關(guān)鍵字和排序方法進(jìn)行升序或降序排序。后面的例13.7也是調(diào)用該函數(shù)對(duì)結(jié)構(gòu)數(shù)組排序。使用該函數(shù)，要求用戶定義一個(gè)比較函數(shù)，程序中函數(shù)cmp是用來(lái)比較大小的函數(shù)，按要求的關(guān)鍵字順序比較各種獎(jiǎng)牌數(shù)，前者多于后者，返回正數(shù)，當(dāng)獎(jiǎng)牌數(shù)一樣時(shí)，調(diào)用標(biāo)準(zhǔn)庫(kù)函數(shù)strcmp比較國(guó)家名稱字符串。源程序\ex13_6.c2/5/202337華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組13.5.2貪心法很多貪心算法的題目里都要用到排序。貪心法也叫做貪婪法，是求解最優(yōu)化問(wèn)題的常用方法之一。它是在求解問(wèn)題時(shí)總作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇，并期望通過(guò)每次所做的局部最優(yōu)選擇產(chǎn)生出一個(gè)全局最優(yōu)解。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。貪心是一種解決問(wèn)題的策略，而不是算法，做出貪心決策的依據(jù)稱為貪心策略。歸納、分析和選擇正確合適的貪心策略，是正確解決貪心問(wèn)題的關(guān)鍵。如果策略正確，貪心法往往編程簡(jiǎn)單、運(yùn)行效率高。2/5/202338華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組貪心法求最優(yōu)裝載問(wèn)題來(lái)看一個(gè)最優(yōu)裝載問(wèn)題：給出n個(gè)物品及其重量，要求選擇盡量多的物品，使總重量不超過(guò)C。由于只關(guān)心物體的數(shù)量，人們會(huì)不假思索地選出一個(gè)最輕的物品裝入；然后從剩下的物品中選出一個(gè)最輕的裝入；如此一直做下去。每次拿最輕的，就是貪心，它只顧眼前，但卻能得到最優(yōu)解。按照“重量最輕者先裝”的貪心策略，只需把所有物品按重量從小到大排序，依次選擇每個(gè)物品，直至裝不下為止。最后編程實(shí)現(xiàn)的核心是排序算法。2/5/202339華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組【例13.7】給出n（n≤50）個(gè)整數(shù)，將它們按某種順序連接成一排，要求最終組成一個(gè)最大的多位整數(shù)。例如，n=4時(shí)，4個(gè)整數(shù)為7、13、4和246，連接成的最大整數(shù)為7424613此題可以用貪心法來(lái)求解。容易想到的貪心策略是：高位數(shù)字大的整數(shù)先取出放前面。對(duì)于7、13、4和246四個(gè)整數(shù)，先取7，再取4，然后246，最后13，連起來(lái)就是7424613，肯定是最優(yōu)解。按此策略，只需將輸入的n個(gè)整數(shù)看作字符串，字符串從大到小排序。但是，當(dāng)整數(shù)相互包含時(shí)，如12、121，按照剛才的貪心策略，先121，后12，組成12112，而實(shí)際應(yīng)該組成12121。因此，剛才的貪心策略不對(duì)。由于不論怎么連接，最終得到整數(shù)的位數(shù)總是相同的，所以比較大小的方式，相當(dāng)于比較連接后的整數(shù)對(duì)應(yīng)的字符串的字典序大小。2/5/202340華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組正確的貪心策略正確的貪心策略是：先把整數(shù)化成字符串，然后再比較a+b和b+a（“+”表示字符串連接），如果(a+b)>(b+a)，就把a(bǔ)排在b的前面，反之則把a(bǔ)排在b的后面。所以，自定義一種字符串的比較規(guī)則：即如果(a+b)>(b+a)，則認(rèn)為a>b。只需要按照這種規(guī)則給n個(gè)字符串排序即可。這樣一來(lái)，程序就很簡(jiǎn)單了，分3步：①把n個(gè)整數(shù)轉(zhuǎn)化為字符串存入一個(gè)字符串?dāng)?shù)組當(dāng)中；②按照自定義的規(guī)則把n個(gè)字符串排序（比較兩個(gè)字符串大小的函數(shù)非常關(guān)鍵）；③輸出排序后的數(shù)組，這個(gè)輸出就是答案。源程序\ex13_7.c2/5/202341華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組在實(shí)際應(yīng)用中，經(jīng)常需要永久保存大量數(shù)據(jù)，這些數(shù)據(jù)通常以文件的形式存儲(chǔ)在硬盤當(dāng)中。對(duì)磁盤文件中數(shù)據(jù)排序的一般思路是：將數(shù)據(jù)全部導(dǎo)入內(nèi)存；用插入、歸并和冒泡等排序方法對(duì)內(nèi)存中的數(shù)據(jù)進(jìn)行排序；將排好序的數(shù)據(jù)存入文件。但是，當(dāng)數(shù)據(jù)量大到不適合在內(nèi)存中排序時(shí)，就要利用磁盤進(jìn)行外排序，這就是海量數(shù)據(jù)的排序問(wèn)題。13.5.3海量數(shù)據(jù)的排序2/5/202342華中科技大學(xué)計(jì)算機(jī)學(xué)院C語(yǔ)言課程組分段排序假如一個(gè)文件中有8億個(gè)整數(shù)，整數(shù)之間用空格分開，要求對(duì)這個(gè)文件進(jìn)行排序。8億個(gè)整數(shù)（1個(gè)整數(shù)為4字節(jié)）需要800000000*4=3.2GB內(nèi)存，一般的設(shè)備沒(méi)有這么多的物理內(nèi)存，無(wú)法將將數(shù)據(jù)完全導(dǎo)入到內(nèi)存中。對(duì)于海量數(shù)據(jù)的排序，最常用的解決方案是分段排序，排序過(guò)程分以下兩階段：第一階段：從磁盤中讀入M（十萬(wàn)級(jí)）條記錄到內(nèi)存，在內(nèi)存排序，將排好序的數(shù)據(jù)存入臨時(shí)文件，重復(fù)該過(guò)程n次，共生成n個(gè)臨時(shí)文件。第二階段：使用多路歸并將n個(gè)臨時(shí)文件中的數(shù)據(jù)按序存入輸出文件。該分段