第8章數(shù)據(jù)結(jié)構(gòu)排序技術(shù)

第八章排序技術(shù)本章的基本內(nèi)容是：排序的基本概念插入排序交換排序選擇排序歸并排序概述

排序：給定一組記錄的集合{r1,r2,……,rn}，其相應(yīng)的關(guān)鍵碼分別為{k1,k2,……,kn}，排序是將這些記錄排列成順序?yàn)閧rs1,rs2,……,rsn}的一個(gè)序列，使得相應(yīng)的關(guān)鍵碼滿足ks1≤ks2≤……≤ksn（稱為升序）或ks1≥ks2≥……≥ksn（稱為降序）。正序：待排序序列中的記錄已按關(guān)鍵碼排好序。逆序（反序）：待排序序列中記錄的排列順序與排好序的順序正好相反。排序的基本概念排序算法的穩(wěn)定性：假定在待排序的記錄集中，存在多個(gè)具有相同鍵值的記錄，若經(jīng)過排序，這些記錄的相對次序仍然保持不變，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。

概述

排序的基本概念學(xué)號(hào)姓名高數(shù)英語思想品德0001王軍85880002李明64920003湯曉影8586………687278……概述

排序的基本概念單鍵排序：根據(jù)一個(gè)關(guān)鍵碼進(jìn)行的排序；多鍵排序：根據(jù)多個(gè)關(guān)鍵碼進(jìn)行的排序。學(xué)號(hào)姓名高數(shù)英語思想品德0001王軍85880002李明64920003湯曉影8586………687278……按學(xué)號(hào)排序——單鍵排序按成績（高數(shù)＋英語＋思想品德）排序——多鍵排序概述

排序的基本概念設(shè)關(guān)鍵碼分別為k1,k2,…,km，多鍵排序有兩種方法：⑴依次對記錄進(jìn)行m次排序，第一次按k1排序，第二次按k2排序，依此類推。這種方法要求各趟排序所用的算法是穩(wěn)定的；⑵將關(guān)鍵碼k1,k2,…,km分別視為字符串依次首尾連接在一起，形成一個(gè)新的字符串，然后，對記錄序列按新形成的字符串排序。多鍵排序單鍵排序排序的分類1.

內(nèi)排序：在排序的整個(gè)過程中，待排序的所有記錄全部被放置在內(nèi)存中2.外排序：由于待排序的記錄個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部分記錄放置在外存上，整個(gè)排序過程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能得到排序的結(jié)果。概述

排序的基本概念排序的分類1.基于比較：基本操作——關(guān)鍵碼的比較和記錄的移動(dòng)，其最差時(shí)間下限已經(jīng)被證明為Ω（nlog2n）。2.

不基于比較：根據(jù)關(guān)鍵碼的分布特征。概述

排序的基本概念基于比較的內(nèi)排序1.插入排序2.交換排序3.選擇排序4.歸并排序1.基本操作。內(nèi)排序在排序過程中的基本操作：⑴比較：關(guān)鍵碼之間的比較；⑵移動(dòng)：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。2.輔助存儲(chǔ)空間。輔助存儲(chǔ)空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序記錄占用的存儲(chǔ)空間之外，執(zhí)行算法所需要的其他存儲(chǔ)空間。3.算法本身的復(fù)雜程度。

排序算法的性能概述

排序算法的存儲(chǔ)結(jié)構(gòu)概述

從操作角度看，排序是線性結(jié)構(gòu)的一種操作，待排序記錄可以用順序存儲(chǔ)結(jié)構(gòu)或鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。假定2：將待排序的記錄序列排序?yàn)樯蛐蛄小?/p>

intr[n+1];//待排序記錄存儲(chǔ)在r[1]~r[n]，r[0]留做他用假定1：采用順序存儲(chǔ)結(jié)構(gòu)，關(guān)鍵碼為整型，且記錄只有關(guān)鍵碼一個(gè)數(shù)據(jù)項(xiàng)。插入排序插入排序的主要操作是插入，其基本思想是：每次將一個(gè)待排序的記錄按其關(guān)鍵碼的大小插入到一個(gè)已經(jīng)排好序的有序序列中，直到全部記錄排好序?yàn)橹?。基本思想：在插入第i（i＞1）個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序。直接插入排序插入排序有序序列無序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……基本思想：在插入第i（i＞1）個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序。（1）如何構(gòu)造初始的有序序列？（2）如何查找待插入記錄的插入位置?直接插入排序插入排序需解決的關(guān)鍵問題?直接插入排序過程示例

r0123456211825221025*212125插入排序i=218221025*25i=318221025*2225222110252115102525*2521151025*252118151018181025*i=418i=61825*i=5r[0]的作用?暫存單元監(jiān)視哨解決方法：將第1個(gè)記錄看成是初始有序表，然后從第2個(gè)記錄起依次插入到這個(gè)有序表中，直到將第n個(gè)記錄插入。插入排序關(guān)鍵問題(1)如何構(gòu)造初始的有序序列？算法描述：for(i=2;i<=n;i++){

插入第i個(gè)記錄，即第i趟直接插入排序；}關(guān)鍵問題(2)如何查找待插入記錄的插入位置?解決方法：在i-1個(gè)記錄的有序區(qū)r[1]~r[i-1]中插入記錄r[i]，首先順序查找r[i]的正確插入位置，然后將r[i]插入到相應(yīng)位置。r[0]有兩個(gè)作用：1.進(jìn)入循環(huán)之前暫存了r[i]的值，使得不致于因記錄的后移而丟失r[i]的內(nèi)容；2.在查找插入位置的循環(huán)中充當(dāng)哨兵。插入排序算法描述：r[0]=r[i];j=i-1; while(r[0]<r[j]){r[j+1]=r[j];

j--;}voidinsertSort(intr[],intn){ for(i=2;i<=n;i++){r[0]=r[i];j=i-1;while(r[0]<r[j]){r[j+1]=r[j]; j=j-1; }r[j+1]=r[0]; }}直接插入排序算法插入排序如果r[i]>=r[i-1]，內(nèi)層循環(huán)會(huì)出現(xiàn)什么情況?直接插入排序算法性能分析最好情況下（正序）：

插入排序12345時(shí)間復(fù)雜度為O(n)。比較次數(shù)：n-1移動(dòng)次數(shù)：2(n-1)123451234512345123452345直接插入排序算法性能分析插入排序最好情況下（正序）：

比較次數(shù)：n-1移動(dòng)次數(shù)：2(n-1)

最壞情況下（逆序或反序）：時(shí)間復(fù)雜度為O(n2)。54321453213452123451123454321比較次數(shù)：移動(dòng)次數(shù)：2)1)(2(2-+=?=nnini2)1)(4(1-+=+?nnin2=i）（時(shí)間復(fù)雜度為O(n)。平均情況下（隨機(jī)排列）：

直接插入排序算法性能分析插入排序時(shí)間復(fù)雜度為O(n2)。比較次數(shù)：移動(dòng)次數(shù)：4)1)(4(-+=?nnn2=i4)1)(2(2-+=?=nnnii2（21+i）空間性能：需要一個(gè)記錄的輔助空間。直接插入排序算法是一種穩(wěn)定的排序算法。直接插入排序算法性能分析插入排序直接插入排序算法簡單、容易實(shí)現(xiàn)，適用于待排序記錄基本有序或待排序記錄較小時(shí)。當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比較和移動(dòng)操作使直接插入排序算法的效率降低。插入排序如何改進(jìn)直接插入排序?注意到，在插入第i（i＞1）個(gè)記錄時(shí)，前面的i-1個(gè)記錄已經(jīng)排好序，則在尋找插入位置時(shí)，可以用折半查找來代替順序查找，從而較少比較次數(shù)。請同學(xué)們寫出這個(gè)改進(jìn)的直接插入排序算法，并分析時(shí)間性能。希爾排序改進(jìn)的著眼點(diǎn)：（1）若待排序記錄按關(guān)鍵碼基本有序時(shí)，直接插入排序的效率可以大大提高；（2）由于直接插入排序算法簡單，則在待排序記錄數(shù)量n較小時(shí)效率也很高。

插入排序（1）應(yīng)如何分割待排序記錄，才能保證整個(gè)序列逐步向基本有序發(fā)展？（2）子序列內(nèi)如何進(jìn)行直接插入排序？插入排序需解決的關(guān)鍵問題?基本思想：將整個(gè)待排序記錄分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，對全體記錄進(jìn)行直接插入排序。希爾排序基本有序：接近正序，例如{1,2,8,4,5,6,7,3,9}；局部有序：部分有序，例如{6,7,8,9,1,2,3,4,5}。局部有序不能提高直接插入排序算法的時(shí)間性能。插入排序希爾排序分割待排序記錄的目的?1.減少待排序記錄個(gè)數(shù)；2.使整個(gè)序列向基本有序發(fā)展。子序列的構(gòu)成不能是簡單地“逐段分割”，而是將相距某個(gè)“增量”的記錄組成一個(gè)子序列。啟示?希爾插入排序過程示例

1234567894021254925*16初始序列插入排序300813d=44021254925*16300813252125*300849131640d=21325210825*16304940252125*300813164049d=10825211325*16304049082513162125*403049解決方法：將相隔某個(gè)“增量”的記錄組成一個(gè)子序列。增量應(yīng)如何??？希爾最早提出的方法是d1=n/2，di+1=di/2。關(guān)鍵問題(1)應(yīng)如何分割待排序記錄？插入排序算法描述：for(d=n/2;d>=1;d=d/2){以d為增量，進(jìn)行組內(nèi)直接插入排序；}解決方法：在插入記錄r[i]時(shí)，自r[i-d]起往前跳躍式（跳躍幅度為d）搜索待插入位置，并且r[0]只是暫存單元，不是哨兵。當(dāng)搜索位置＜0，表示插入位置已找到。在搜索過程中，記錄后移也是跳躍d個(gè)位置。在整個(gè)序列中，前d個(gè)記錄分別是d個(gè)子序列中的第一個(gè)記錄，所以從第d+1個(gè)記錄開始進(jìn)行插入。插入排序關(guān)鍵問題(2)子序列內(nèi)如何進(jìn)行直接插入排序？算法描述：for(i=d+1;i<=n;i++)//將r[i]插入到所屬的子序列中{

r[0]=r[i];//暫存待插入記錄j=i-d;//j指向所屬子序列的最后一個(gè)記錄while(j>0&&r[0]<r[j]){r[j+d]=r[j];//記錄后移d個(gè)位置j=j-d;//比較同一子序列的前一個(gè)記錄}r[j+d]=r[0];}插入排序關(guān)鍵問題(2)子序列內(nèi)如何進(jìn)行直接插入排序？希爾排序算法的時(shí)間性能希爾排序算法的時(shí)間性能是所取增量的函數(shù)，而到目前為止尚未有人求得一種最好的增量序列。研究表明，希爾排序的時(shí)間性能在O(n2)和O(nlog2n)之間。當(dāng)n在某個(gè)特定范圍內(nèi)，希爾排序所需的比較次數(shù)和記錄的移動(dòng)次數(shù)約為O(n1.3)

。插入排序希爾排序開始時(shí)增量較大，每個(gè)子序列中的記錄個(gè)數(shù)較少，從而排序速度較快；當(dāng)增量較小時(shí)，雖然每個(gè)子序列中記錄個(gè)數(shù)較多，但整個(gè)序列已基本有序，排序速度也較快。

交換排序的主要操作是交換，其主要思想是：在待排序列中選兩個(gè)記錄，將它們的關(guān)鍵碼相比較，如果反序（即排列順序與排序后的次序正好相反），則交換它們的存儲(chǔ)位置。

交換排序反序則交換rirj起泡排序基本思想：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。

rj

rj+1ri+1≤……

≤rn-1≤rn

無序區(qū)有序區(qū)1≤j≤i-1已經(jīng)位于最終位置反序則交換交換排序05981269385381起泡排序過程示例

交換排序059812693853810598126938538105981269385381⑴在一趟起泡排序中，若有多個(gè)記錄位于最終位置，應(yīng)如何記載？⑵如何確定起泡排序的范圍，使得已經(jīng)位于最終位置的記錄不參與下一趟排序？⑶如何判別起泡排序的結(jié)束？交換排序需解決的關(guān)鍵問題?起泡排序解決方法：設(shè)變量exchange記載記錄交換的位置，則一趟排序后，exchange記載的一定是這一趟排序中記錄的最后一次交換的位置，且從此位置以后的所有記錄均已經(jīng)有序。交換排序關(guān)鍵問題⑴：如何記載一趟排序過程中交換的多個(gè)記錄？059812693853810598698112交換38交換53交換交換排序關(guān)鍵問題⑴：如何記載一趟排序過程中交換的多個(gè)記錄？算法描述：if（r[j]>r[j+1]）{r[j]←→r[j+1]；exchange=j；}解決方法：設(shè)變量exchange記載記錄交換的位置，則一趟排序后，exchange記載的一定是這一趟排序中記錄的最后一次交換的位置，且從此位置以后的所有記錄均已經(jīng)有序。解決方法：設(shè)bound位置的記錄是無序區(qū)的最后一個(gè)記錄，則每趟起泡排序的范圍是r[1]~r[bound]。在一趟排序后，從exchange位置之后的記錄一定是有序的，所以bound=exchange。交換排序關(guān)鍵問題⑵：如何確定起泡排序的范圍？059812693853810598698112交換38交換53交換解決方法：設(shè)bound位置的記錄是無序區(qū)的最后一個(gè)記錄，則每趟起泡排序的范圍是r[1]~r[bound]。在一趟排序后，從exchange位置之后的記錄一定是有序的，所以bound=exchange。交換排序關(guān)鍵問題⑵：如何確定起泡排序的范圍？算法描述：bound=exchange;for(j=1;j<bound;j++) if（r[j]>r[j+1]）{r[j]<==>r[j+1]；exchange=j；}05981269385381解決方法：在每一趟起泡排序之前，令exchange的初值為0，在以后的排序過程中，只要有記錄交換，exchange的值就會(huì)大于0。這樣，在一趟比較完畢，就可以通過exchange的值是否為0來判別是否有記錄交換，從而判別整個(gè)起泡排序的結(jié)束。交換排序關(guān)鍵問題⑶：如何判別起泡排序的結(jié)束？解決方法：在每一趟起泡排序之前，令exchange的初值為0，在以后的排序過程中，只要有記錄交換，exchange的值就會(huì)大于0。這樣，在一趟比較完畢，就可以通過exchange的值是否為0來判別是否有記錄交換，從而判別整個(gè)起泡排序的結(jié)束。交換排序關(guān)鍵問題⑶：如何判別起泡排序的結(jié)束？算法描述：while(exchange){執(zhí)行一趟起泡排序；}voidBubbleSort(intr[],intn){ exchange=n; while(exchange){

bound=exchange;exchange=0；for(j=1;j<bound;j++)if(r[j]>r[j+1]){r[j]←→r[j+1]； exchange=j；}}}起泡排序算法交換排序起泡排序的時(shí)間性能分析最好情況（正序）：交換排序比較次數(shù)：n-1移動(dòng)次數(shù)：0

12345時(shí)間復(fù)雜度為O(n)。12345最壞情況（反序）：起泡排序的時(shí)間性能分析最好情況（正序）：交換排序比較次數(shù)：n-1移動(dòng)次數(shù)：0

54321時(shí)間復(fù)雜度為O(n)；時(shí)間復(fù)雜度為O(n2)。43215321452134512345比較次數(shù)：移動(dòng)次數(shù)：2)1(1-=?=nn(n-i)n-1i2)1(1-=?=n3n3(n-i)n-1i平均情況：時(shí)間復(fù)雜度為O(n2)。交換排序如何改進(jìn)起泡排序?12345需掃描1趟54321需掃描n-1趟51234需掃描2趟23451需掃描n-2趟造成不對稱的原因是什么?交換排序如何改變不對稱性?23451在排序過程中交替改變掃描方向——雙向起泡排序2341512345快速排序改進(jìn)的著眼點(diǎn)：在起泡排序中，記錄的比較和移動(dòng)是在相鄰單元中進(jìn)行的，記錄每次交換只能上移或下移一個(gè)單元，因而總的比較次數(shù)和移動(dòng)次數(shù)較多。交換排序減少總的比較次數(shù)和移動(dòng)次數(shù)增大記錄的比較和移動(dòng)距離較大記錄從前面直接移動(dòng)到后面較小記錄從后面直接移動(dòng)到前面快速排序的基本思想首先選一個(gè)軸值（即比較的基準(zhǔn)），通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，前一部分記錄的關(guān)鍵碼均小于或等于軸值，后一部分記錄的關(guān)鍵碼均大于或等于軸值，然后分別對這兩部分重復(fù)上述方法，直到整個(gè)序列有序。交換排序⑴如何選擇軸值？⑵如何實(shí)現(xiàn)分割（稱一次劃分）？⑶如何處理分割得到的兩個(gè)待排序子序列？⑷如何判別快速排序的結(jié)束？需解決的關(guān)鍵問題?選擇軸值的方法：1.使用第一個(gè)記錄的關(guān)鍵碼；2.選取序列中間記錄的關(guān)鍵碼；3.比較序列中第一個(gè)記錄、最后一個(gè)記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個(gè)記錄的位置；4.隨機(jī)選取軸值。交換排序關(guān)鍵問題⑴：如何選擇軸值？選取不同軸值的后果：決定兩個(gè)子序列的長度，子序列的長度最好相等。13652750384955ji1338652750495513652750493855交換排序關(guān)鍵問題⑵：如何實(shí)現(xiàn)一次劃分？jjiiijijjj解決方法：設(shè)待劃分的序列是r[s]~r[t]，設(shè)參數(shù)i，j分別指向子序列左、右兩端的下標(biāo)s和t，令r[s]為軸值，（1）j從后向前掃描，直到r[j]<r[i]，將r[j]移動(dòng)到r[i]的位置，使關(guān)鍵碼小（同軸值相比）的記錄移動(dòng)到前面去；（2）i從前向后掃描，直到r[i]＞r[j]，將r[i]移動(dòng)到r[j]的位置，使關(guān)鍵碼大（同軸值比較）的記錄移動(dòng)到后面去；（3）重復(fù)上述過程，直到i=j。交換排序關(guān)鍵問題⑵：如何實(shí)現(xiàn)一次劃分？交換排序關(guān)鍵問題⑵：如何實(shí)現(xiàn)一次劃分？算法描述：intPartition(intr[],intfirst,intend){ i=first;j=end;//初始化while(i<j) {while(i<j&&r[i]<=r[j])j--；//右側(cè)掃描

if(i<j){r[i]←→r[j];i++;//將較小記錄交換到前面}while(i<j&&r[i]<=r[j])i++；//左側(cè)掃描if(i<j){r[j]←→r[i];j--;//將較大記錄交換到后面}}retutni;//i為軸值記錄的最終位置}解決方法：對分割得到的兩個(gè)子序列遞歸地執(zhí)行快速排序。交換排序關(guān)鍵問題⑶：如何處理分割得到的兩個(gè)待排序子序列？

1327386550495513275038495565ijij算法描述：交換排序關(guān)鍵問題⑶：如何處理分割得到的兩個(gè)待排序子序列？

voidQuickSort(intr[],intfirst,intend){pivotpos=Partition(r,first,end);//一次劃分QuickSort(r,first,pivotpos-1);//對前一個(gè)子序列進(jìn)行快速排序QuickSort(r,pivotpos+1,end);//對后一個(gè)子序列進(jìn)行快速排序}解決方法：若待排序列中只有一個(gè)記錄，顯然已有序，否則進(jìn)行一次劃分后，再分別對分割所得的兩個(gè)子序列進(jìn)行快速排序（即遞歸處理）。

交換排序關(guān)鍵問題⑷：如何判別快速排序的結(jié)束？

voidQuickSort(intr[],intfirst,intend){//在序列first~end中遞歸地進(jìn)行快速排序

if(first<end){ pivotpos=Partition(r,first,end);QuickSort(r,first,pivotpos-1);QuickSort(r,pivotpos+1,end);}}算法描述：交換排序關(guān)鍵問題⑷：如何判別快速排序的結(jié)束？

交換排序例：{38,27,55,50,13,49,65}的快速排序遞歸樹如下：38135055496527快速排序的遞歸執(zhí)行過程可以用遞歸樹描述?？焖倥判虻臅r(shí)間性能分析快速排序的時(shí)間性能分析交換排序快速排序的時(shí)間性能快速排序遞歸的深度每次劃分軸值的選取最好情況：每一次劃分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)?？焖倥判虻臅r(shí)間性能分析交換排序T(n)≤2T(n/2)＋n≤2(2T(n/4)＋n/2)＋n＝4T(n/4)＋2n≤4(2T(n/8)＋n/4)＋2n＝8T(n/8)＋3n………≤nT(1)＋nlog2n＝O(nlog2n)最壞情況：每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列（另一個(gè)子序列為空），為O(n2)。最好情況：每一次劃分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)。快速排序的時(shí)間性能分析交換排序平均情況：為O(nlog2n)。)()1(21211nOnninni=-=-?-=）（選擇排序的主要操作是選擇，其主要思想是：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵碼最小的記錄，添加到有序序列中。

選擇排序有序序列r1r2ri-1rirnrk…………無序序列rnri+1r1r2ri-1……riri……交換最小記錄簡單選擇排序基本思想：第i趟在n-i+1（i=1,2,…,n-1）個(gè)記錄中選取關(guān)鍵碼最小的記錄作為有序序列中的第i個(gè)記錄。

選擇排序需解決的關(guān)鍵問題?⑴如何在待排序序列中選出關(guān)鍵碼最小的記錄？⑵如何確定待排序序列中關(guān)鍵碼最小的記錄在有序序列中的位置？

簡單選擇排序示例0821i=2最小者08交換21,08最小者16交換25,16最小者21交換49,212128i=12516490808i=32108284921選擇排序28491625161625i=4最小者25交換25,28i=5最小者28不交換選擇排序簡單選擇排序示例492108281625254921081628252849210816282528無序區(qū)只有一個(gè)記錄解決方法：設(shè)置一個(gè)整型變量index，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。

選擇排序關(guān)鍵問題⑴：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？212825164908indexindexindex08算法描述：index=i; for(j=i+1;j<=n;j++)

if(r[j]<r[index])index=j;解決方法：設(shè)置一個(gè)整型變量index，用于記錄在一趟比較的過程中關(guān)鍵碼最小的記錄位置。

關(guān)鍵問題⑴：如何在無序區(qū)中選出關(guān)鍵碼最小的記錄？解決方法：第i趟簡單選擇排序的待排序區(qū)間是r[i]~r[n]，則r[i]是無序區(qū)第一個(gè)記錄，所以，將index所記載的關(guān)鍵碼最小的記錄與r[i]交換。選擇排序關(guān)鍵問題⑵：如何確定最小記錄的最終位置？算法描述：

if(index!=i)

r[i]←→r[index]; voidselectSort(intr[],intn){for(i=1;i<n;i++){

index=i; for(j=i+1;j<=n;j++)if(r[j]<r[index])index=j;if(index!=i)r[i]<==>r[index]; }}簡單選擇排序算法選擇排序簡單選擇排序算法的性能分析移動(dòng)次數(shù)：最好情況（正序）：0次選擇排序12345123451234512345123451234最壞情況：3(n-1)次簡單選擇排序算法的性能分析移動(dòng)次數(shù)：最好情況（正序）：0次選擇排序空間性能：需一個(gè)輔助空間。穩(wěn)定性：是一種穩(wěn)定的排序算法。45231152341253412354123451234比較次數(shù)：)()1(21211nOnninni=-=-?-=）（簡單選擇排序的時(shí)間復(fù)雜度為O(n2)。堆排序改進(jìn)的著眼點(diǎn)：如何減少關(guān)鍵碼間的比較次數(shù)。若能利用每趟比較后的結(jié)果，也就是在找出鍵值最小記錄的同時(shí)，也找出鍵值較小的記錄，則可減少后面的選擇中所用的比較次數(shù)，從而提高整個(gè)排序過程的效率。選擇排序減少關(guān)鍵碼間的比較次數(shù)查找最小值的同時(shí)，找出較小值堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。選擇排序182032364525385040281.小根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最小者。2.較小結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（稱為小根堆），或每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（稱為大根堆）。選擇排序503845402836322018281.大根堆的根結(jié)點(diǎn)是所有結(jié)點(diǎn)的最大者。2.較大結(jié)點(diǎn)靠近根結(jié)點(diǎn)，但不絕對。堆和序列的關(guān)系選擇排序?qū)⒍延庙樞虼鎯?chǔ)結(jié)構(gòu)來存儲(chǔ)，則堆對應(yīng)一組序列。503845402836322018285038453236402820182812345678910采用順序存儲(chǔ)基本思想：首先將待排序的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄的最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個(gè)記錄。

選擇排序堆排序需解決的關(guān)鍵問題?⑴如何由一個(gè)無序序列建成一個(gè)堆（即初始建堆）？⑵如何處理堆頂記錄？⑶如何調(diào)整剩余記錄，成為一個(gè)新堆（即重建堆）？

堆調(diào)整堆調(diào)整：在一棵完全二叉樹中，根結(jié)點(diǎn)的左右子樹均是堆，如何調(diào)整根結(jié)點(diǎn)，使整個(gè)完全二叉樹成為一個(gè)堆？選擇排序283632161825321618253628voidsift(intr[],intk,intm){//要篩選結(jié)點(diǎn)的編號(hào)為k，堆中最后一個(gè)結(jié)點(diǎn)的編號(hào)為mi=k;j=2*i;temp=r[i];//將篩選記錄暫存

while(j<=m)//篩選還沒有進(jìn)行到葉子{

if(j<m&&r[j]<r[j+1])j++;//左右孩子中取較大者if(r[i]>r[j])break;else{r[i]=r[j];i=j;j=2*i;}}r[i]=temp;//將篩選記錄移到正確位置}選擇排序堆調(diào)整——算法描述：選擇排序關(guān)鍵問題⑴：如何由一個(gè)無序序列建成一個(gè)堆？282516321836163216282518362532162818362528323628161825算法描述：for(i=n/2;i>=1;i--)

sift(r,i,n);

選擇排序關(guān)鍵問題⑴：如何由一個(gè)無序序列建成一個(gè)堆？最后一個(gè)結(jié)點(diǎn)（葉子）的序號(hào)是n，則最后一個(gè)分支結(jié)點(diǎn)即為結(jié)點(diǎn)n的雙親，其序號(hào)是n/2。選擇排序關(guān)鍵問題⑵：如何處理堆頂記錄？323628161825362832251816123456對應(yīng)交換162832251836123456對應(yīng)321628361825算法描述：r[1]←→r[n-i+1];

選擇排序關(guān)鍵問題⑵：如何處理堆頂記錄？解決方法：第i次處理堆頂是將堆頂記錄r[1]與序列中第n-i+1個(gè)記錄r[n-i+1]交換。321628361825選擇排序關(guān)鍵問題⑶：如何調(diào)整剩余記錄，成為一個(gè)新堆？16281632361825283236181625解決方法：第

i次調(diào)整剩余記錄，此時(shí)，剩余記錄有n-i個(gè)，調(diào)整根結(jié)點(diǎn)至第n-i個(gè)記錄。選擇排序關(guān)鍵問題⑶：如何調(diào)整剩余記錄，成為一個(gè)新堆？算法描述：sift(r,1,n-i);堆排序算法voidHeapSort(intr[],intn){for(i=n/2;i>=1;i--)//初建堆

sift(r,i,n);for(i=1;i>n;i++){

r[1]←→r[n-i+1];//移走堆頂sift(r,1,n-i);//重建堆}}選擇排序堆排序算法的性能分析第1個(gè)for循環(huán)是初始建堆，需要O(n)時(shí)間；第2個(gè)for循環(huán)是輸出堆頂重建堆，共需要取n-1次堆頂記錄，第i次取堆頂記錄重建堆需要O(log2i)時(shí)間，需要O(nlog2n)時(shí)間；因此整個(gè)時(shí)間復(fù)雜度為O(nlog2n)，這是堆排序的最好、最壞和平均的時(shí)間代價(jià)。選擇排序歸并排序歸并排序的主要操作是歸并，其主要思想是：將若干有序序列逐步歸并，最終得到一個(gè)有序序列。

歸并排序歸并：將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列的過程。基本思想：將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長度為1的有序序列，然后進(jìn)行兩兩歸并，得到n/2個(gè)長度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4個(gè)長度為4的有序序列，……，直至得到一個(gè)長度為n的有序序列為止。二路歸并排序歸并排序需解決的關(guān)鍵問題?⑴如何將兩個(gè)有序序列合成一個(gè)有序序列？⑵怎樣完成一趟歸并？⑶如何控制二路歸并的結(jié)束？關(guān)鍵問題⑴：如何將兩個(gè)有序序列合成一個(gè)有序序列？歸并排序60203154455652060531445565

6020315445565ij5kj20i31j60關(guān)鍵問題⑴：如何將兩個(gè)有序序列合成一個(gè)有序序列？歸并排序60203154455652060531445565

6020315445565ij5kj20i31j60歸并可以就地進(jìn)行嗎?在歸并過程中，可能會(huì)破壞原來的有序序列，所以，將歸并的結(jié)果存入另外一個(gè)數(shù)組中。關(guān)鍵問題⑴：如何將兩個(gè)有序序列合成一個(gè)有序序列？歸并排序60203154455652060531445565

6020315445565ij5kj20i31j60關(guān)鍵問題⑴：如何將兩個(gè)有序序列合成一個(gè)有序序列？歸并排序60203154455652060531445565

6020315445565ij5kj20i31j60子序列的長度一定相等嗎?關(guān)鍵問題⑴：如何將兩個(gè)有序序列合成一個(gè)有序序列？歸并排序60203154455652060531445565

6020315445565ij5kj20i31j60關(guān)鍵問題⑴：如何將兩個(gè)有序序列合成一個(gè)有序序列？歸并排序設(shè)相鄰的有序序列為r[s]~r[m]和r[m+1]~r[t]，歸并成一個(gè)有序序列r1[s]~r1[t]smm+1tr[]str1[]ijkvoidMerge(intr[],intr1[],ints,intm,intt){i=s;j=m+1;k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}if(i<=m)while(i<=m)//收尾處理r1[k++]=r[i++];//前一個(gè)子序列elsewhile(j<=t)r1[k++]=r[j++];//后一個(gè)子序列}歸并排序關(guān)鍵問題⑴：如何將兩個(gè)有序序列合成一個(gè)有序序列？算法描述：歸并排序關(guān)鍵問題⑵：怎樣完成一趟歸并？602031544556520605314455656020315445565

5203160

445565在一趟歸并中，除最后一個(gè)有序序列外，其它有序序列中記錄的個(gè)數(shù)相同，用長度h表示。歸并排序關(guān)鍵問題⑵：怎樣完成一趟歸并？設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：①若i≤n-2h+1，則相鄰兩個(gè)有序表的長度均為h，執(zhí)行一次歸并，完成后i加2h，準(zhǔn)備進(jìn)行下一次歸并；2060531445565ihi=1n-2h+1=4n-2h+1歸并排序關(guān)鍵問題⑵：怎樣完成一趟歸并？設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：①若i≤n-2h+1，則相鄰兩個(gè)有序表的長度均為h，執(zhí)行一次歸并，完成后i加2h，準(zhǔn)備進(jìn)行下一次歸并；算法描述：while(i≤n-2h+1){Merge(r,r1,i,i+h-1,i+2*h-1);i+=2*h;}歸并排序關(guān)鍵問題⑵：怎樣完成一趟歸并？設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：②若i＜n-h+1，則表示仍有兩個(gè)相鄰有序表，一個(gè)長度為h，另一個(gè)長度小于h，則執(zhí)行兩個(gè)有序表的歸并，完成后退出一趟歸并。2060531445565ihi=4n-2h+1=4n-h+1=6n-2h+1n-h+1<h歸并排序關(guān)鍵問題⑵：怎樣完成一趟歸并？設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：②若i＜n-h+1，則表示仍有兩個(gè)相鄰有序表，一個(gè)長度為h，另一個(gè)長度小于h，則執(zhí)行兩個(gè)有序表的歸并，完成后退出一趟歸并。算法描述：if(i＜n-h+1)Merge(r,r1,i,i+h-1,n);歸并排序關(guān)鍵問題⑵：怎樣完成一趟歸并？設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：③若i≥n-h+1，則表明只剩下一個(gè)有序表，直接將該有序表送到r1的相應(yīng)位置，完成后退出一趟歸并。

ii=9n-h+1=8n-h+1h20605314455651528歸并排序關(guān)鍵問題⑵：怎樣完成一趟歸并？設(shè)參數(shù)i指向待歸并序列的第一個(gè)記錄，歸并的步長是2h，在歸并過程中，有以下三種情況：③若i≥n-h+1，則表明只剩下一個(gè)有序表，直接將該有序表送到r1的相應(yīng)位置，完成后退出一趟歸并。

算法描述：if(i>=n-h+1)for(k=i;k<=n;k++)r1[k]=r[k];

voidMergePass(intr[],intr1[],intn,inth){i=1;while(i≤n-2h+1)//情況1{