數(shù)據(jù)結(jié)構(gòu)第23次課-排序D

1、每課一貼： 古之立大事者，不惟有超世之才，亦必有堅忍不拔之志。 蘇軾有志者，事竟成，破釜沉舟，百二雄關(guān)終屬楚；苦心人，天不負，臥薪嘗膽，三千越甲可吞吳。 蒲松齡13.選擇排序簡單選擇排序： 排序過程:選擇未排序序列中最小者與該序列第一個元素交換算法評價時間復雜度記錄移動次數(shù)最好情況：0 (正序）最壞情況：3(n-1) （逆序）比較次數(shù)：空間復雜度：S(n)=O(1)穩(wěn)定性：不穩(wěn)定，反例2，2，1 T(n)=O(n)上節(jié)課內(nèi)容回顧24. 選擇排序堆排序 堆的定義：n個元素的序列(k1,k2,kn)，當且僅當滿足下列關(guān)系時，稱之為堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik

2、2i+1小根堆 大根堆 堆排序：將無序序列建成一個堆，輸出堆頂并重構(gòu)堆，重復執(zhí)行即可得到有序序列，這個過程叫關(guān)鍵問題解決方法篩選 方法：輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并與其中小者進行交換；重復上述操作，直至葉子結(jié)點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”3建堆方法方法：從無序序列的第n/2個元素（即此無序序列對應的完全二叉樹的最后一個非終端結(jié)點）起，至第一個元素止，進行反復篩選4算法描述int sift(int r , int k, int m) /篩選, k-篩選元素編號, m 結(jié)點總數(shù) int i, j; int x

3、; i=k; x=ri; j=2*i; while(j=m) /未比較到最后一層 /若左子樹大則和右子樹比較，否則和左子樹比,j表示待比較較小關(guān)鍵字子樹編號 if( (jrj+1 ) ) j+; if( xrj ) /大于較小子樹的關(guān)鍵字，交換后繼續(xù)篩選 ri=rj; /子結(jié)點上移一層 i= j; /待篩選結(jié)點更新 j= i*2; /子樹結(jié)點編號更新 else j=m+1; /否則篩選完成，終止循環(huán) ri=x; /插入數(shù)據(jù) 5算法描述void heapsort(int r , int n) /堆排序 int i; int x; for( i=n/2; i=1; i-) /建堆，依次篩選前面n/

4、2個結(jié)點 sift(r,i,n); for(i=n;i=2;i-) /取堆頂元素輸出，再篩選,實現(xiàn)排序操作 x=r1; r1=ri; ri=x; sift(r,1,i-1); 6算法評價時間復雜度：最壞情況下T(n)=O(nlog2n)空間復雜度：S(n)=O(1)穩(wěn)定性：不穩(wěn)定7練習： 含8個元素的無序序列： （ 51， 47，39，25，87，96，43，17）試構(gòu)建一個小根堆，并給出排序過程中堆的變化過程5139474396872517173925439687475189.1 插入排序9.2 交換排序9.3 選擇排序9.4 歸并排序9.5 基數(shù)排序9.6 小結(jié)(各類排序方法比較）第9章

5、排序9歸并將兩個或兩個以上的有序表組合成一個新的有序表，叫2-路歸并排序算法基本思路： 設兩個有序的子文件(相當于輸入堆)放在同一向量中相鄰的位置上：Rlow.m，Rm+1.high，先將它們合并到一個局部的暫存向量R1(相當于輸出堆)中，待合并完成后將R1復制回Rlow.high中。 9.4 歸并排序10 A.設置i，j和p三個指針，其初值分別指向這三個記錄區(qū)的起始位置; B.合并時依次比較Ri和Rj的關(guān)鍵字，取關(guān)鍵字較小的記錄復制到R1p中; C.然后將被復制記錄的指針i或j加1，以及指向復制位置的指針p加1。 D. 重復這一過程直至兩個輸入的子文件有一個已全部復制完畢(不妨稱其為空)，此

6、時將另一非空的子文件中剩余記錄依次復制到R1中即可。 合并過程11設初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列長度為1兩兩合并，得到n/2 個長度為2或1的有序子序列再兩兩合并，如此重復，直至得到一個長度為n的有序序列為止排序過程12例初始關(guān)鍵字： 49 38 65 97 76 13 27一趟歸并后： 38 49 65 97 13 76 27二趟歸并后： 38 49 65 97 13 27 76三趟歸并后： 13 27 38 49 65 76 9713算法描述void MergeSortDC(SeqList R，int low，int high) /用分治法對Rlow.high

7、進行二路歸并排序 int mid； if(lowhigh) /區(qū)間長度大于1 mid=(low+high)/2； /分解 MergeSortDC(R，low，mid); /遞歸地對Rlow.mid排序 MergeSortDC(R，mid+1，high)； /遞歸地對Rmid+1.high排序 Merge(R，low，mid，high)； /組合,將兩個有序區(qū)歸并為一個有序區(qū) /MergeSortDC14void Merge(SeqList R，int low，int m，int high) /將兩個有序的子文件Rlow.m和Rm+1.high歸并成一個有序的 /子文件Rlow.high int

8、 i=low，j=m+1，p=0； /置初始值 while(i=m&j=high) /兩子文件非空時取其小者輸出到R1p上 R1p+=( Ri= Rj ) ? Ri+ ：Rj+； while(i=m) /若第1個子文件非空，則復制剩余記錄到R1中 R1p+=Ri+； while(j=high) /若第2個子文件非空，則復制剩余記錄到R1中 R1p+=Rj+； for(p=0，i=low；i=high；p+，i+) Ri=R1p；/歸并完成后將結(jié)果復制回Rlow.high /Merge15算法評價時間復雜度：T(n)=O(nlog2n)空間復雜度：S(n)=O(n) 因為需要一個輔助向量來暫存兩

9、有序子文件歸并的結(jié)果穩(wěn)定性：穩(wěn)定169.5 基數(shù)排序例 對52張撲克牌按以下次序排序：23A23A23A23A兩個關(guān)鍵字：花色（ ） 面值（ 23A）并且“花色”地位高于“面值”多關(guān)鍵字排序基數(shù)排序基本思路： 基數(shù)排序不需要和前面的排序方法那樣進行關(guān)鍵字的比較和移動，它是一種借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行排序的方法。17多關(guān)鍵字排序方法最高位優(yōu)先法（MlD)：先對最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個子序列有相同的k1值；然后讓每個子序列對次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復，直至就每個子序列對最低位關(guān)鍵字kd排序；最后將所有子序列依次連接

10、成為一個有序序列.最低位優(yōu)先法(LlD)：從最低位關(guān)鍵字kd起進行排序，然后再對高一位的關(guān)鍵字排序，依次重復，直至對最高位關(guān)鍵字k1排序后，便成為一個有序序列. MlD與LlD不同特點按MlD排序，必須將序列逐層分割成若干子序列，然后對各子序列分別排序按LlD排序，不必分成子序列，對每個關(guān)鍵字都是整個序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實現(xiàn)排序.18鏈式基數(shù)排序基數(shù)排序：借助“分配”和“收集”對單邏輯關(guān)鍵字進行排序的一種方法. 單邏輯關(guān)鍵字可以看成由多個關(guān)鍵字復合而成的，例如若關(guān)鍵字是數(shù)值，且都在0999之間，則可以把每個十進制數(shù)字看成一個關(guān)鍵字，位權(quán)越高的關(guān)鍵字優(yōu)先程

11、度越高。對應的基數(shù)就是關(guān)鍵字的取值范圍10。如果關(guān)鍵字由5個字母組成呢？ 關(guān)鍵字可取5個，基數(shù)取26。 鏈式基數(shù)排序：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序19鏈式基數(shù)排序步驟(對3位10進制數(shù)):設置10個隊列，fi和ei分別為第i個隊列的頭指針和尾指針第一趟分配對最低位關(guān)鍵字（個位）進行，改變記錄的指針值，將鏈表中記錄分配至10個鏈隊列中，每個隊列記錄的關(guān)鍵字的個位相同第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將10個隊列鏈成一個鏈表重復上述兩步，進行第二趟、第三趟分配和收集，分別對十位、百位進行，最后得到一個有序序列20例初始狀態(tài)：278109063930

12、589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：21505008109930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：220080630831091842692785055

13、89930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：23鏈式基數(shù)排序步驟(對3位10進制數(shù)):設置10個隊列，fi和ei分別為第i個隊列的頭指針和尾指針第一趟分配對最低位關(guān)鍵字（個位）進行，改變記錄的指針值，將鏈表中記錄分配至10個鏈隊列中，每個隊列記錄的關(guān)鍵字的個位相同第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將10個隊列鏈成一個鏈表重復上述兩步，進行第二趟、第三趟

14、分配和收集，分別對十位、百位進行，最后得到一個有序序列24算法 描述int radixsort ( JD r , int n ) int i,j,k,t,p,rd,rg,f10,e10; for(i=1;in;i+) ri.link=i+1; rn.link=0; p=1; rd=1; rg=10; for(i=1;i=D;i+) /D為關(guān)鍵字，執(zhí)行D次分配和收集 for(j=0;j0); j=0; while(fj=0) j+; p=fj; t=ej; for(k=j+1;k0) rt.link=fk; t=ek; rt.link=0; rg= rg*10; rd= rd *10; retu

15、rn(p); 25算法評價時間復雜度：分配：T(n)=O(n)收集：T(n)=O(rd) T(n)=O(d(n+rd) 其中：n記錄數(shù) d關(guān)鍵字數(shù) rd關(guān)鍵字取值范圍 空間復雜度：S(n)=O(rd) 2rd個隊列指針穩(wěn)定性： 穩(wěn)定269.6 各種排序算法的比較排序要求掌握的基本知識基本實現(xiàn)思路時間和空間復雜度穩(wěn)定性排序算法的應用場合27直接插入排序： 第一個元素有序，其他元素依次插入希爾排序：縮小增量分組排序法冒泡排序：兩兩比較，一趟排序使最小(大)元素定位快速排序：通過樞軸將序列分成兩部分，遞歸執(zhí)行簡單選擇排序：找未排序序列中最小者與第一個元素交換堆排序： 借助堆來實現(xiàn)排序，基本操作輸出和

16、篩選歸并排序： 借助二路歸并思路進行排序基數(shù)排序： 多關(guān)鍵字序列排序，多次分配與收集基本實現(xiàn)思路：28練習：已知待排序的關(guān)鍵字序列是36，5，32，98，95，47， 32，3，48請回答：(1)若采用直接插入排序，第一個位置前移的元素關(guān)鍵字是？ (2) 若采用希爾排序（di5,3,1）, 第一個位置前移的元素關(guān)鍵字是？ (3)若采用直接選擇排序，第一個位置前移的元素關(guān)鍵字是？ (4)若采用快速排序，第一個位置前移的元素關(guān)鍵字是？(5) 若采用堆排序，建堆過程中第一次篩選交換的兩個元素關(guān)鍵字是？29時間、空間復雜度、穩(wěn)定性30 直接插入排序、冒泡排序、簡單選擇排序合稱簡單排序，其特點是平均時間

17、復雜度和最壞時間復雜度都是O(n2) ，空間復雜度O(1) 。31 幾點結(jié)論： 從平均時間性能而言，快速排序最佳，其所需時間最省，但快速排序在最壞情況下的時間性能不如堆排序和歸并排序。而后兩者相比較的結(jié)果是，在n較大時，歸并排序所需時間較堆排序省，但它所需的輔助存儲量最多。 簡單排序算法中以直接插入排序為最簡單，當序列中的記錄“基本有序”或n值較小時，它是最佳的排序方法，因此常將它和其它的排序方法，諸如快速排序、歸并排序等結(jié)合在一起使用。32 基數(shù)排序的時間復雜度也可寫成O(dn)。因此，它最適用于n值很大而關(guān)鍵字較小的序列。若關(guān)鍵字也很大，而序列中大多數(shù)記錄的“最高位關(guān)鍵字”均不同，則亦可先

18、按“最高位關(guān)鍵字”不同將序列分成若干“小“的子序列后進行直接插入排序。 從方法的穩(wěn)定性來比較，一般來說，排序過程中的“比較”是在“相鄰的兩個記錄關(guān)鍵字”間進行的排序方法是穩(wěn)定的。由于大多數(shù)情況下排序是按記錄的主關(guān)鍵字進行的，則所用的排序方法是否穩(wěn)定無關(guān)緊要。若排序按記錄的次關(guān)鍵字進行，則應根據(jù)問題所需慎重選擇排序方法及其描述算法。33 本章討論的多數(shù)排序算法是在順序存儲結(jié)構(gòu)上實現(xiàn)的，因此在排序過程中需進行大量記錄的移動。當記錄很大(即每個記錄占空間較多)時，時間耗費很大，此時可采用靜態(tài)鏈表作存儲結(jié)構(gòu)。如表插入排序、鏈式基數(shù)排序，以修改指針代替移動記錄。 當無法實現(xiàn)表排序的時候，可以進行“地址排序”，即另設一個地址向量指示相應記錄；同時在排序過程中不移動記錄而移動地址向量中相應分量的內(nèi)容。34 綜上所述，在本章討