C語言與程序設計ppt-第13章

C語言與程序設計

TheCandProgramming

第13章排序

華中科技大學計算機學院

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

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

2/5/20232華中科技大學計算機學院C語言課程組13.1直接插入排序直接插入排序的基本思想是：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經(jīng)排好序的子序列中的適當位置，直到全部記錄插入為止。具體過程為：假設待排序的n個記錄存放在數(shù)組a中，a被劃分成兩個子區(qū)：有序區(qū)(a[0]～a[i-1])和無序區(qū)(a[i]～a[n-1])。開始時，i=1，即有序區(qū)中只包含1個元素a[0]，無序區(qū)中包含有n-1個元素(a[1]～a[n-1])。排序過程中每次從無序區(qū)中取出第1個元素a[i]，將它插入到有序區(qū)中的適當位置，使a[0]～a[i]成為新的有序區(qū)，重復n-1次可完成排序過程。因為這種方法每次使有序區(qū)增加1個記錄，通常稱增量法。2/5/20233華中科技大學計算機學院C語言課程組直接插入排序的過程圖13.1給出a={25,10,45,75,15}時的直接插入排序過程，其中大括號內(nèi)為有序區(qū)，后面為無序區(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直接插入排序的過程2/5/20234華中科技大學計算機學院C語言課程組【例13.1】編程實現(xiàn)直接插入排序算法要求計算機生成若干個3位的隨機整數(shù)，放入數(shù)組，完成對數(shù)組的升序排序。分析：本實例要完成兩個功能：①產(chǎn)生隨機數(shù)放入數(shù)組；②對數(shù)組排序。按照結構化程序設計思想，分別定義函數(shù)CreateData和InsertSort實現(xiàn)這兩個功能,然后編寫主函數(shù)main對程序功能進行測試，輸出排序結果。2/5/20235華中科技大學計算機學院C語言課程組函數(shù)CreateData由于需要產(chǎn)生在兩個極限值之間取值的數(shù)據(jù)，為了使函數(shù)CreateData有通用性，函數(shù)原型為：

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

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

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