選擇和基數排序

1、選擇排序和基數排序選擇排序和基數排序選擇排序的基本思想簡單選擇排序堆選擇排序小結和作業(yè)基數排序選擇排序的基本思想選擇排序的基本思想選擇排序的基本思想：選擇排序的基本思想：每一趟從待排序的每一趟從待排序的n-i+1（i=1,2,3,n-1）個記個記錄錄中選出中選出關鍵字最小關鍵字最小的記錄，作為有序序列中的記錄，作為有序序列中第第i個記錄個記錄，直到全部記錄排序完畢。，直到全部記錄排序完畢。1. 1. 直接選擇排序直接選擇排序2. 2. 堆選擇排序堆選擇排序簡單選擇排序簡單選擇排序-基本思想基本思想假設排序過程中，待排記錄序列的狀態(tài)為：假設排序過程中，待排記錄序列的狀態(tài)為：有序序列有序序列R1.

2、i-1R1.i-1無序序列無序序列 Ri.nRi.n 第第 i i 趟趟簡單選擇排序簡單選擇排序從中選出從中選出關鍵字最小的記錄關鍵字最小的記錄有序序列有序序列R1.iR1.i無序序列無序序列 Ri+1.nRi+1.n簡單選擇排序簡單選擇排序-基本思想基本思想第第i趟排序過程：趟排序過程：1）第）第i趟排序開始時，當前有序區(qū)和無序區(qū)分別為趟排序開始時，當前有序區(qū)和無序區(qū)分別為R1.i-1和和Ri.n；2）該趟排序從當前無序區(qū)中選出關鍵字最小的記錄）該趟排序從當前無序區(qū)中選出關鍵字最小的記錄Rk，將它與無序區(qū)的第，將它與無序區(qū)的第1個記錄個記錄Ri交換交換3）使）使R1.i和和Ri+1.n分別變

3、為記錄個數增加分別變?yōu)橛涗泜€數增加1個的個的新有序區(qū)和記錄個數減少新有序區(qū)和記錄個數減少1個的新無序區(qū)個的新無序區(qū) 4913簡單選擇排序簡單選擇排序-例子例子6597 76132738 1 2 3 4 5 6 7 kjkjjjjkj49第一趟第一趟i=113i13簡單選擇排序簡單選擇排序-例子例子6597 76492738 1 2 3 4 5 6 7kj第二趟：第二趟：i=2jjjjk273827i13簡單選擇排序簡單選擇排序-例子例子6597 764938 1 2 3 4 5 6 7第三趟：第三趟：i=3j2765kjjj38k38136597 764965 1 2 3 4 5 6 7第四趟

4、：第四趟：i=42738974949iik簡單選擇排序簡單選擇排序-例子例子136597 769765 1 2 3 4 5 6 7第五趟：第五趟：i=5273838497665136597 769776 1 2 3 4 5 6 7第六趟：第六趟：i=627383849766597136597 769797 1 2 3 4 5 6 7排序結果：排序結果：27383849766597ii簡單選擇排序簡單選擇排序-算法算法void SelectSort (Elem R, int n ) / 對記錄序列對記錄序列R1.n作簡單選擇排序。作簡單選擇排序。 for (i=1; i0; -i ) HeapA

5、djust ( H.r, i, H.length ); / 建大頂堆for ( i=H.length; i1; -i ) H.r1H.ri; / 將堆頂記錄和當前未經排序子序列 / H.r1.i中最后一個記錄相互交換 HeapAdjust(H.r, 1, i-1); / 對 H.r1 進行篩選堆排序堆排序堆篩選算法堆篩選算法void HeapAdjust (RcdType &R, int s, int m) / 已知 Rs.m中記錄的關鍵字除 Rs 之外均 / 滿足堆的特征，本函數自上而下調整 Rs 的 / 關鍵字，使 Rs.m 也成為一個大頂堆 / HeapAdjustrc = Rs; /

6、暫存 Rs for ( j=2*s; j= Rj.key ) break; / 再作“根”和“子樹根”之間的比較， / 若“=”成立，則說明已找到 rc 的插 / 入位置 s ，不需要繼續(xù)往下調整Rs = Rj; s = j; / 否則記錄上移，尚需繼續(xù)往下調整if ( jm & Rj.keyRj+1.key ) +j; / 左/右“子樹根”之間先進行相互比較 / 令 j 指示關鍵字較大記錄的位置堆排序堆排序-性能分析性能分析1. 對深度為對深度為 k 的堆，的堆，“篩選篩選”所需進行的關鍵字所需進行的關鍵字比較的次數至多為比較的次數至多為2(k-1)；2. 對對 n 個關鍵字，建成深度為個關

7、鍵字，建成深度為h(= log2n +1)的堆，的堆，所需進行的關鍵字比較的次數至多所需進行的關鍵字比較的次數至多 4n；堆排序堆排序-性能分析性能分析3. 調整“堆頂” n-1 次，總共進行的關鍵字比較的次數不超過 2 ( log2(n-1) + log2(n-2) + +log22) 2n( log2n ) 因此，堆排序的時間復雜度為因此，堆排序的時間復雜度為O(nlogn)。堆排序的平均性能較接近于最壞性能。堆排序的平均性能較接近于最壞性能。輔助空間為O(1) 4.堆排序是一個不穩(wěn)定的排序方法。堆排序是一個不穩(wěn)定的排序方法。堆排序堆排序-課堂練習課堂練習2、請回答下列關于堆的問題a.堆的

8、存儲表示是順序的還是鏈式的？b.設有一個最小堆，即堆中任意結點的關鍵字都大于它的左右子女的關鍵字。其具有最大值的元素可能在什么地方c. 對n個元素進行初始見堆的過程中，最多做多少次數據比較?；鶖蹬判蚧鶖蹬判蚧鶖蹬判蚴且环N基數排序是一種借助借助“多關鍵字排序多關鍵字排序”的思的思想來實現(xiàn)想來實現(xiàn)“單關鍵字排序單關鍵字排序”的內部排序算法。的內部排序算法。1.1.多關鍵字的排序多關鍵字的排序2.2.鏈式基數排序鏈式基數排序多關鍵字排序多關鍵字排序n 個記錄的序列個記錄的序列 R1, R2, ，Rn對對關鍵字關鍵字 (Ki0, Ki1,Kid-1) 有序有序是指： 對于序列中任意兩個記錄 Ri 和

9、Rj(1ijn) 都滿足滿足下列(詞典詞典)有序有序關系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1) 其中其中: K0 被稱為被稱為 “最主最主”位關鍵位關鍵字字Kd-1 被稱為被稱為 “最次最次”位關鍵字位關鍵字多關鍵字排序多關鍵字排序1.最高位優(yōu)先最高位優(yōu)先MSD法先對先對K0進行排序進行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K1 進行排序，.， 依次類推，直至最后對最次位關鍵字排序完成為直至最后對最次位關鍵字排序完成為止止。多關鍵字排序多關鍵字排序2.最低位優(yōu)先最低位優(yōu)先LSD法法先對先對 Kd-1 進行排序，然后對進行排序，然

10、后對 Kd-2 進行排序，依次類推，直至對最主位關鍵字直至對最主位關鍵字 K0 排序完成排序完成為止為止。多關鍵字排序多關鍵字排序學生記錄含三個關鍵字:系別系別、班號班號和班內的班內的序列號序列號，其中以系別為最主位關鍵字。LSD的排序過程如下: 無序序列無序序列對對K2排序排序對對K1排序排序對對K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30鏈式基數排序鏈式基數排序假如多關鍵字的記錄序列

11、中，每個關鍵字的取值范假如多關鍵字的記錄序列中，每個關鍵字的取值范圍相同，則按圍相同，則按LSD法進行排序時，可以采用法進行排序時，可以采用“分配分配-收集收集”的方法，其好處是不需要進行關鍵字間的比的方法，其好處是不需要進行關鍵字間的比較。較。對于數字型或字符型的單關鍵字單關鍵字，可以看成看成是由多個數位或多個字符構成的多關鍵字多關鍵字，此時可以采用采用這種“分配分配-收集收集”的辦法進行排序進行排序，稱作稱作基數排序法基數排序法。鏈式基數排序鏈式基數排序例如：例如：對下列這組關鍵字對下列這組關鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 1.

12、首先按其首先按其 “個位數個位數” 取值分別為取值分別為 0, 1, , 9 “分配分配” 成成 10 組，之后按從組，之后按從 0 至至 9 的順序將它們的順序將它們 “收集收集” 在一起；在一起；鏈式基數排序鏈式基數排序初始狀態(tài)：初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配一趟分配930063083184505278008109589269一趟收集：一趟收集：鏈式基數排序鏈式基數排序2.然后按其 “十位數” 取值分別為

13、 0, 1, , 9 “分配分配” 成 10 組，之后再按從 0 至 9 的順序將它們 “收集收集” 在一起；鏈式基數排序鏈式基數排序930063083184505278008109589269083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配二趟分配008109278505008109930063269278083184589二趟收集：二趟收集：鏈式基數排序鏈式基數排序3.3.最后按其最后按其“百位數百位數”重復一遍上述操作。重復一遍上述操作。008063083109184269278505589930三三趟趟收

14、收集集109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配三趟分配063083269278505589505008109930063269278083184589鏈式基數排序鏈式基數排序有此可知，在計算機上實現(xiàn)基數排序時，為減少所有此可知，在計算機上實現(xiàn)基數排序時，為減少所需輔助存儲空間，應采用鏈表作存儲結構需輔助存儲空間，應采用鏈表作存儲結構，即鏈式，即鏈式基數排序，具體作法為：基數排序，具體作法為：待排序記錄以指針相鏈，構成一個鏈表；待排序記錄以指針相鏈，構成一個鏈表；“分配分配”時，按當前時，按當前“關鍵字位關鍵字位”所取值，所

15、取值，將記錄分配到不同的將記錄分配到不同的“鏈隊列鏈隊列”中，每個隊列中，每個隊列中記錄的中記錄的“關鍵字位關鍵字位”相同；相同；鏈式基數排序鏈式基數排序“收集收集”時，按當前關鍵字位取值從小時，按當前關鍵字位取值從小到大到大將各隊列首尾相鏈成一個鏈表將各隊列首尾相鏈成一個鏈表; ;對每個關鍵字位均重復對每個關鍵字位均重復 2) 2) 和和 3) 3) 兩步。兩步。鏈式基數排序鏈式基數排序“分配分配”和和“收集收集”的實際操作僅為修改鏈的實際操作僅為修改鏈表中的指針和設置隊列的頭、尾指針；表中的指針和設置隊列的頭、尾指針；為查找使用，該鏈表尚需應用算法為查找使用，該鏈表尚需應用算法Arrang

16、e Arrange 將它調整為有序表。將它調整為有序表。鏈式基數排序鏈式基數排序-性能分析性能分析 基數排序的時間復雜度為基數排序的時間復雜度為O(d(n+rd)其中：分配為其中：分配為O(n) 收集為收集為O(rd)(rd為為“基基”) d為為“分配分配-收集收集”的趟數的趟數基數排序是穩(wěn)定的排序方法基數排序是穩(wěn)定的排序方法小結和作業(yè)小結和作業(yè)簡單選擇簡單選擇排序排序 堆排序堆排序1 1基本思想基本思想 3 3算法算法2 2實例模擬實例模擬 4 4時間復雜度時間復雜度1 1基本思想基本思想 3 3算法算法2 2實例模擬實例模擬 4 4時間復雜度時間復雜度基數排序基數排序 1 1基本思想基本思想 3 3算法算法2 2實例模擬實例模擬 4 4時間復雜度時間復雜度選擇排序選擇排序 小結和作業(yè)小結和作業(yè)重點：重點： 1）算法的設計思想；）算法的設計思想； 2）手工排序方法；）手工排序方法； 3）算法的時間復雜度和空間復雜度。）算法的時間復雜度和空間復雜度。作業(yè)：作業(yè)：10.1(4，6)，10.12 討論：堆排序的優(yōu)缺點。討論：堆排序的優(yōu)缺點。人有了知識，就會具備各種分析能力，人有了知識，就會具備各種分析能力，明辨是非的能力。明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀