數(shù)據(jù)結(jié)構(gòu)教學(xué)課件：Chapter Nine Sorting1

1、數(shù)據(jù)結(jié)構(gòu)Chapter Nine Sorting引基本術(shù)語插入排序交換排序選擇排序 堆排序(Heap Sort) 二路歸并排序 基數(shù)排序外排序 排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。 數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)對象的有限集合。關(guān)鍵碼(key): 通常數(shù)據(jù)對象有多個(gè)屬性域，即多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來區(qū)分對象，作為排序依據(jù)。該域即為關(guān)鍵碼。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為關(guān)鍵碼，要視具體的應(yīng)用需要而定。即使是同一個(gè)表，在解決不同問題的場合也可能取不同的域做關(guān)鍵碼。1、基本術(shù)語主關(guān)鍵碼: 如果在數(shù)據(jù)表中各個(gè)對象的關(guān)鍵碼互不相同，這種關(guān)鍵碼即主關(guān)鍵碼。按照主關(guān)

2、鍵碼進(jìn)行排序，排序的結(jié)果是唯一的。次關(guān)鍵碼: 數(shù)據(jù)表中有些對象的關(guān)鍵碼可能相同，這種關(guān)鍵碼稱為次關(guān)鍵碼。按照次關(guān)鍵碼進(jìn)行排序，排序的結(jié)果可能不唯一。排序算法的穩(wěn)定性: 如果在對象序列中有兩個(gè)對象ri和rj，它們的關(guān)鍵碼 ki = kj，且在排序之前，對象ri排在rj前面。如果在排序之后，對象ri仍在對象rj的前面，則稱這個(gè)排序方法是穩(wěn)定的，否則稱這個(gè)排序方法是不穩(wěn)定的。1、基本術(shù)語內(nèi)排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對象個(gè)數(shù)太多，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序。排序的時(shí)間開銷: 排序的時(shí)間開銷是衡

3、量算法好壞的最重要的標(biāo)志。排序的時(shí)間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。各節(jié)給出算法運(yùn)行時(shí)間代價(jià)的大略估算一般都按平均情況進(jìn)行估算。對于那些受對象關(guān)鍵碼序列初始排列及對象個(gè)數(shù)影響較大的，需要按最好情況和最壞情況進(jìn)行估算。1、基本術(shù)語靜態(tài)排序: 排序的過程是對數(shù)據(jù)對象本身進(jìn)行物理地重排，經(jīng)過比較和判斷，將對象移到合適的位置。這時(shí)，數(shù)據(jù)對象一般都存放在一個(gè)順序的表中。動態(tài)排序: 給每個(gè)對象增加一個(gè)鏈接指針，在排序的過程中不移動對象或傳送數(shù)據(jù)，僅通過修改鏈接指針來改變對象之間的邏輯順序，從而達(dá)到排序的目的。算法執(zhí)行時(shí)所需的附加存儲: 評價(jià)算法好壞的另一標(biāo)準(zhǔn)。靜態(tài)排序過程中所用到的數(shù)

4、據(jù)表類定義，體現(xiàn)了抽象數(shù)據(jù)類型的思想。1、基本術(shù)語基本思想：2、插入排序每步將一個(gè)待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。包括：直接插入排序 (Insert Sort)折半插入排序(Binary Insert sort)鏈表插入排序希爾排序 (Shell Sort)直接插入排序 (Insert Sorting)2、插入排序基本思想：僅有一個(gè)記錄的表總是有序的，因此，對n個(gè)記錄的表，可從第二個(gè)記錄開始直到第n個(gè)記錄，逐個(gè)向有序表中進(jìn)行插入操作，從而得到n個(gè)記錄按關(guān)鍵碼有序的表。8.1 插入排序直接插入排序排序過程：整個(gè)排序過程為n-1趟插入

5、，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序算法描述2、插入排序例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97

6、)排序結(jié)果：算法評價(jià)時(shí)間復(fù)雜度若待排序記錄按關(guān)鍵字從小到大排列(正序)關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：若待排序記錄按關(guān)鍵字從大到小排列(逆序)關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：若待排序記錄是隨機(jī)的，取平均值關(guān)鍵字比較次數(shù)：記錄移動次數(shù)：T(n)=O(n)空間復(fù)雜度：S(n)=O(1)折半插入排序排序過程：用折半查找方法確定插入位置的排序叫例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20

7、 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )算法描述算法評價(jià)時(shí)間復(fù)雜度：T(n)=O(n)空間復(fù)雜度：S(n)=O(1)希爾排序(縮小增量法)排序過程：先取一個(gè)正整數(shù)d1n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2r2.key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后

8、一個(gè)記錄上對前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止例49 38 65 97 76 13 27 30初始關(guān)鍵字38 49 65 76 13 27 30 97第一趟38 49 65 13 27 30 76第二趟38 49 13 27 30 65第三趟38 13 27 30 49第四趟13 27 30 38第五趟13 27 30第六趟38497697139727973097137676762730136527653065131349493049273827383038算法描述算法評價(jià)時(shí)間復(fù)雜

9、度最好情況（正序）比較次數(shù)：n-1移動次數(shù)：0最壞情況（逆序）比較次數(shù)：移動次數(shù)：空間復(fù)雜度：S(n)=O(1)T(n)=O(n)Ch8_4.c快速排序基本思想：通過一趟排序，將待排序記錄分割成獨(dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄進(jìn)行排序，以達(dá)到整個(gè)序列有序排序過程：對rst中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針i和j，設(shè)樞軸記錄rp=rs，x=rp.key初始時(shí)令i=s,j=t首先從j所指位置向前搜索第一個(gè)關(guān)鍵字小于x的記錄，并和rp交換再從i所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于x的記錄，和rp交換重復(fù)上述兩步，直至i=j為止再分別對兩個(gè)子

10、序列進(jìn)行快速排序，直到每個(gè)子序列只含有一個(gè)記錄為止例初始關(guān)鍵字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進(jìn)行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結(jié)束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij算法描述算法評價(jià)時(shí)間復(fù)雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n)空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸最壞情況：S(

11、n)=O(n)一般情況：S(n)=O(log2n)T(n)=O(n)Ch8_5.c8.3 選擇排序簡單選擇排序排序過程首先通過n-1次關(guān)鍵字比較，從n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換再通過n-2次比較，從剩余的n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié)束例初始： 49 38 65 97 76 13 27 kjjjjjjkki=11349一趟： 13 38 65 97 76 49 27 i=2kkjjjjj2738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 1

12、3 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 13 27 38 49 65 76 97 排序結(jié)束： 13 27 38 49 65 76 97算法描述算法評價(jià)時(shí)間復(fù)雜度記錄移動次數(shù)最好情況：0最壞情況：3(n-1)比較次數(shù)：空間復(fù)雜度：S(n)=O(1)T(n)=O(n)Ch8_6.c堆排序堆的定義：n個(gè)元素的序列(k1,k2,kn)，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例 （96，83，27，38，11，9）例 （13，38，27，50，76，65，49，97）962791

13、138831327384965765097可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個(gè)元素的最小值或最大值堆排序：將無序序列建成一個(gè)堆，得到關(guān)鍵字最小（或最大）的記錄；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余的n-1個(gè)元素重又建成一個(gè)堆，則可得到n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列，這個(gè)過程叫堆排序需解決的兩個(gè)問題：如何由一個(gè)無序序列建成一個(gè)堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？第二個(gè)問題解決方法篩選方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將

14、得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選”例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13 273849502765769713輸出：13 276549502738769713輸出：13 27 384965502738769713輸出：13 27 387665502738499713輸出：13 27 38 495065762738499713輸出：13 27 38 499765762738495013輸出：13 27 38 49 506597762738495013輸出：13

15、 27 38 49 509765762738495013輸出：13 27 38 49 50 657665972738495013輸出：13 27 38 49 50 659765762738495013輸出：13 27 38 49 50 65 769765762738495013輸出：13 27 38 49 50 65 76 97算法描述第一個(gè)問題解決方法方法：從無序序列的第n/2個(gè)元素（即此無序序列對應(yīng)的完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選例 含8個(gè)元素的無序序列（49，38，65，97，76，13，27，50）496538271376975049653827137

16、65097491338276576509749133827657650971327384965765097算法描述算法評價(jià)時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlogn)空間復(fù)雜度：S(n)=O(1)Ch8_7.c8.4 歸并排序歸并將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表，叫2-路歸并排序排序過程設(shè)初始序列含有n個(gè)記錄，則可看成n個(gè)有序的子序列，每個(gè)子序列長度為1兩兩合并，得到n/2個(gè)長度為2或1的有序子序列再兩兩合并，如此重復(fù)，直至得到一個(gè)長度為n的有序序列為止例初始關(guān)鍵字： 49 38 65 97 76 13 27一趟歸并后： 38 49 65 97 13 76 27二趟歸并后： 3

17、8 49 65 97 13 27 76三趟歸并后： 13 27 38 49 65 76 97算法描述算法評價(jià)時(shí)間復(fù)雜度：T(n)=O(nlog2n)空間復(fù)雜度：S(n)=O(n)Ch8_9.c8.5 基數(shù)排序多關(guān)鍵字排序定義：例 對52張撲克牌按以下次序排序：23A23A23A23A兩個(gè)關(guān)鍵字：花色（ ） 面值（23A）并且“花色”地位高于“面值”多關(guān)鍵字排序方法最高位優(yōu)先法（MSD)：先對最高位關(guān)鍵字k1（如花色）排序，將序列分成若干子序列，每個(gè)子序列有相同的k1值；然后讓每個(gè)子序列對次關(guān)鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復(fù)，直至就每個(gè)子序列對最低位關(guān)鍵字kd排序；最后將

18、所有子序列依次連接在一起成為一個(gè)有序序列最低位優(yōu)先法(LSD)：從最低位關(guān)鍵字kd起進(jìn)行排序，然后再對高一位的關(guān)鍵字排序，依次重復(fù)，直至對最高位關(guān)鍵字k1排序后，便成為一個(gè)有序序列MSD與LSD不同特點(diǎn)按MSD排序，必須將序列逐層分割成若干子序列，然后對各子序列分別排序按LSD排序，不必分成子序列，對每個(gè)關(guān)鍵字都是整個(gè)序列參加排序；并且可不通過關(guān)鍵字比較，而通過若干次分配與收集實(shí)現(xiàn)排序鏈?zhǔn)交鶖?shù)排序基數(shù)排序：借助“分配”和“收集”對單邏輯關(guān)鍵字進(jìn)行排序的一種方法鏈?zhǔn)交鶖?shù)排序：用鏈表作存儲結(jié)構(gòu)的基數(shù)排序鏈?zhǔn)交鶖?shù)排序步驟設(shè)置10個(gè)隊(duì)列，fi和ei分別為第i個(gè)隊(duì)列的頭指針和尾指針第一趟分配對最低位關(guān)鍵

19、字（個(gè)位）進(jìn)行，改變記錄的指針值，將鏈表中記錄分配至10個(gè)鏈隊(duì)列中，每個(gè)隊(duì)列記錄的關(guān)鍵字的個(gè)位相同第一趟收集是改變所有非空隊(duì)列的隊(duì)尾記錄的指針域，令其指向下一個(gè)非空隊(duì)列的隊(duì)頭記錄，重新將10個(gè)隊(duì)列鏈成一個(gè)鏈表重復(fù)上述兩步，進(jìn)行第二趟、第三趟分配和收集，分別對十位、百位進(jìn)行，最后得到一個(gè)有序序列例初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配930063083184505278008109589269一趟收集：50500810

20、9930063269278083184589二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集：008063083109184269278505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配063083269278505589505008109930063269278083184589二趟收集：算法描述算法評價(jià)時(shí)間復(fù)雜度：分配：T(n)=O(n)收集：T(n)=O(rd)T(