數(shù)據(jù)結(jié)構(gòu)6.4選擇類排序主講人：朱利華常州信息職業(yè)技術(shù)學(xué)院Part01直接選擇排序是一種簡(jiǎn)單直觀的排序算法在排序過程中，所需移動(dòng)記錄的次數(shù)較少，比較適合數(shù)據(jù)規(guī)模小的情況什么是直接選擇排序直接選擇排序從待排序數(shù)據(jù)中，選出最小（最大）的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)中，再找最小（最大）的數(shù)與第二個(gè)位置的數(shù)交換位置；依次類推，直到第n-1個(gè)元素與第n個(gè)元素交換位置，選擇排序結(jié)束。基本思路直接選擇排序每一趟從待排序的數(shù)據(jù)中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，順序放在已排好序的數(shù)列最后；經(jīng)過n-1趟比較，直到全部待排序的數(shù)據(jù)元素排完。基本操作直接選擇排序數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院初始狀態(tài)：無序區(qū)為R[1..n]，有序區(qū)為空；第i趟排序(i=1,2,3…n-1)開始時(shí)，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R[i..n]。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄R[minIndex]，將它與無序區(qū)的第1個(gè)記錄交換，使R[1..i]和R[i+1..n]變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無序區(qū)；n-1趟結(jié)束，得到一個(gè)有序序列。算法描述直接選擇排序算法n個(gè)記錄需n-1趟直接選擇排序得到有序結(jié)果。示例【例6-6】設(shè)待排序的文件有8個(gè)記錄，其關(guān)鍵字分別為：26，53，48，11，13，48，32，15，使用直接選擇排序方法進(jìn)行排序的過程。括號(hào)內(nèi)元素為已排好序元素，括號(hào)外元素是當(dāng)前侯選元素。直接選擇排序初始關(guān)鍵字

26

534811

13

483215第1趟排序找最小元素下標(biāo)iminIndex交換記錄i后移一位2653481113483215[11]26i第2趟排序找余下最小元素下標(biāo)minIndex交換記錄i后移一位[11]534826

13483215[1113]2653第3趟排序找余下最小元素下標(biāo)iminIndex交換記錄i后移一位[1113]4826534832

15[111315]2653

48第4趟排序找余下最小元素下標(biāo)iminIndexi后移一位[11131526]53483248第5趟排序找余下最小元素下標(biāo)3253iminIndex交換記錄i后移一位[111315

26]53

4832482632]53iminIndex第6趟排序找余下最小元素下標(biāo)i后移一位[111315

2632

48]5348第7趟排序找余下最小元素下標(biāo)5348minIndexi交換記錄排序結(jié)束[111315

2632

48

4853算法實(shí)現(xiàn)直接選擇排序//交換兩個(gè)記錄方法publicstaticvoidswap(int[]a,inti,intj){ if(i==j){ return; } a[i]=a[i]+a[j]; a[j]=a[i]-a[j]; a[i]=a[i]-a[j];}//使用直接選擇排序方法實(shí)現(xiàn)整形數(shù)據(jù)元素排序publicstaticvoidselectSort(int[]a){for(inti=0;i<a.length-1;i++){ intminIndex=i;//記錄最小值的索引 for(intj=i+1;j<a.length;j++){ if(a[j]<a[minIndex]){//若后面元素值小于最小值,將j賦值給minIndex minIndex=j; } } if(minIndex!=i){ swap(a,i,minIndex);//交換兩個(gè)元素 }}}算法分析直接選擇排序數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院空間復(fù)雜度S(n)=O(1)穩(wěn)定性不穩(wěn)定排序時(shí)間復(fù)雜度T(n)=O(n2)Part02堆排序1964年由J.W.J.Williams提出是直接選擇排序的改進(jìn)算法改進(jìn)思路：選擇排序中第1趟需比較n?1次，第2趟需比較n?2次，第i趟需比較n-i次，其實(shí)有許多數(shù)據(jù)在前一趟比較中比較過，如能利用以前比較結(jié)果可大大提高排序的效率。什么是堆排序堆排序(1)堆的定義對(duì)于數(shù)據(jù)元素序列｛R1，R2…，Rn｝，當(dāng)且僅當(dāng)滿足下列關(guān)系之一時(shí)，稱之為堆。堆相關(guān)概念堆排序堆頂元素（即第一個(gè)元素）必為最大項(xiàng)或最小項(xiàng)完全二叉樹可直觀表示堆結(jié)構(gòu)，堆是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于（或不小于）其左、右孩子結(jié)點(diǎn)的關(guān)鍵字堆的任一子樹也是堆或kik2i+1kik2i+2kik2i+1kik2i+2(

i=1,2,…...n/2)(2)大根堆和小根堆堆相關(guān)概念堆排序大根堆符合條件②每個(gè)結(jié)點(diǎn)關(guān)鍵字都不小于其孩子結(jié)點(diǎn)的關(guān)鍵字小根堆符合條件①每個(gè)結(jié)點(diǎn)關(guān)鍵字都不大于其孩子結(jié)點(diǎn)的關(guān)鍵字kik2i+1kik2i+2kik2i+1kik2i+2示例【例6-7】對(duì)應(yīng)的元素序列分別為{96，83，27，38，11，9}、{13，38，27，50，76，65，49，97}，分別畫出其完全二叉樹和存儲(chǔ)結(jié)構(gòu)。利用完全二叉樹性質(zhì)，大根堆滿足每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值小根堆滿足每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值堆排序大根堆96279113883邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)小根堆1327384965765097邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)對(duì)一組待排序的記錄序列，先將其關(guān)鍵字按堆的定義排列一個(gè)序列（初建堆），找到了最?。ㄗ畲螅╆P(guān)鍵字，將其取出用剩余的n-1個(gè)元素再重建堆，便可得到次?。ù未螅┲等绱朔磸?fù)執(zhí)行，直到全部關(guān)鍵字排好序?yàn)橹够舅悸范雅判蚪鉀Q兩個(gè)問題：按照堆定義建初堆；去掉最大元素后重建堆，得到次大元素。其步驟如下：基本操作堆排序(1)構(gòu)建初始堆(3)重建堆(2)交換數(shù)據(jù)結(jié)構(gòu)（Java語言描述）常州信息職業(yè)技術(shù)學(xué)院先將初始記錄R[1..N]建成一個(gè)大根堆，此堆為初始的無序區(qū)；再將最大記錄R[1](即堆頂)和無序區(qū)的最后一個(gè)記錄R[n]交換，得到新的無序區(qū)R[1..n-1]和有序區(qū)R[n]，且滿足R[1..n-1].keys≤R[n].key；交換后新根R[1]可能違反堆性質(zhì)，故將無序區(qū)R[1..n-1]調(diào)整為堆，再將R[1..n-1]中最大記錄R[1]和該區(qū)間的最后一個(gè)記錄R[n-1]交換，得到新的無序區(qū)R[1..n-2]和有序區(qū)R[n-1..n]，且仍滿足關(guān)系R[1..n-2].keys≤R[n-1.n].keys，同樣繼續(xù)要將R[1..n-2]調(diào)整為堆；重復(fù)上面兩步，直到無序區(qū)只有一個(gè)元素為止。基本算法堆排序示例【例6-8】給出一組待排序序列{49，38，65，97，76，13，27，50}，使用堆排序方法進(jìn)行排序，分別寫出構(gòu)建初始堆的過程和堆排序的過程。構(gòu)建初始堆堆排序首先由初始序列得到完全二叉樹；從最后一個(gè)非葉子結(jié)點(diǎn)開始，即從97開始，對(duì)97進(jìn)行調(diào)整，從左至右，從下至上進(jìn)行調(diào)整；繼續(xù)從最后第二個(gè)將一個(gè)無序序列構(gòu)造成了一個(gè)小根堆。49653827137697504965382713765097(4)左子樹符合堆49133827657650974913382765765097(5)發(fā)現(xiàn)49比13大，交換。換位置后，和它孩子結(jié)點(diǎn)繼續(xù)比較，49比13大，再次互換。1327384965765097(6)所有父結(jié)點(diǎn)都比孩子結(jié)點(diǎn)小，是小根堆。示例【例6-8】給出一組待排序序列{49，38，65，97，76，13，27，50}，使用堆排序方法進(jìn)行排序，分別寫出構(gòu)建初始堆的過程和堆排序的過程。堆排序過程堆排序4965382713769750(1)初始狀態(tài)1327384965765097(2)創(chuàng)建初始堆1327384965765097(3)交換13和90，“沉下”13沉下：139727384965765013(4)篩選調(diào)整堆2749389765765013沉下：13(5)交換27和97，“沉下”279749382765765013沉下：1327(6)篩選調(diào)整堆3849502765769713沉下：1327(7)交換38和65，沉下38沉下：1327386549502738769713(8)篩選調(diào)整堆4965502738769713沉下：132738(9)交換49和76，“沉下”497665502738499713沉下：13273849(10)篩選調(diào)整堆5065762738499713沉下：13273849(11)交換50和97，“沉下”509765762738495013沉下：1327384950(12)篩選調(diào)整堆9765762738495013沉下：132738495065(14)篩選調(diào)整堆(13)交換65和97，“沉下”656597762738495013沉下：13273849507665972738495013沉下：132738495065(15)交換76和97，“沉下”769765762738495013沉下：13273849506576(16)只有一個(gè)根結(jié)點(diǎn)9765762738495013輸出：1327384950657697(17)順序輸出排序結(jié)果算法實(shí)現(xiàn)堆排序//使用堆排序?qū)φ螖?shù)據(jù)元素進(jìn)行排序publicstaticvoidheapSort(int[]a){heapInsert(a);//構(gòu)造大根堆intsize=a.length;while(size>1){ swap(a,0,size-1);//固定最大值 size--;//待排元素個(gè)數(shù)減少1個(gè) heapify(a,0,size);//余下元素構(gòu)造大根堆}}//構(gòu)造大根堆publicstaticvoidheapInsert(int[]a){for(inti=0;i<a.length;i++){ intcurrentIndex=i;//當(dāng)前插入的索引 intfatherIndex=(currentIndex-1)/2;//父結(jié)點(diǎn)索引//如果當(dāng)前插入值大于其父結(jié)點(diǎn)值時(shí)調(diào)整位置，否則退出循環(huán)while(a[currentIndex]>a[fatherIndex]){ swap(a,currentIndex,fatherIndex);//交換當(dāng)前結(jié)點(diǎn)與父結(jié)點(diǎn)值 currentIndex=fatherIndex;//將當(dāng)前索引指向父索引 fatherIndex=(currentIndex-1)/2;//重新計(jì)算當(dāng)前索引父索引}}}算法實(shí)現(xiàn)堆排序//通過頂端的數(shù)下降，將剩余的數(shù)構(gòu)造成大根堆publicstaticvoidheapify(int[]a,intindex,intsize){intleft=2*index+1;//左孩子intright=2*index+2;//右孩子while(left<size){ intlargestIndex; //判斷孩子中較大的值的索引 if(a[left