數(shù)據(jù)結(jié)構(gòu)第十章ppt課件

1、數(shù)據(jù)構(gòu)造課程的內(nèi)容數(shù)據(jù)構(gòu)造課程的內(nèi)容9.1 9.1 概述概述9.2 9.2 插入排序插入排序9.3 9.3 交換排序交換排序9.4 9.4 選擇排序選擇排序9.5 9.5 歸并排序歸并排序9.6 9.6 基數(shù)排序基數(shù)排序10.1 10.1 概述概述1 1、排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)展的一種操作，其目的是將一、排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)展的一種操作，其目的是將一組組“無序的記錄序列調(diào)整為無序的記錄序列調(diào)整為“按關(guān)鍵字有序的記錄序列按關(guān)鍵字有序的記錄序列。52，49，80，36，14，58，61，23，97，7514，23，36，49，52，58，61，75，80，97普通情況下，普通情況下，假設(shè)含假設(shè)含n

2、n個記錄的序列為個記錄的序列為R1R1，R2R2，RnRn其相應(yīng)的關(guān)鍵字序列為其相應(yīng)的關(guān)鍵字序列為 K1 K1，K2K2，KnKn這些關(guān)鍵字相互之間可以進(jìn)展比較，這些關(guān)鍵字相互之間可以進(jìn)展比較，即在它們之間存在這樣一個關(guān)系：即在它們之間存在這樣一個關(guān)系：Kp1=Kp2=KpnKp1=Kp2=36 )( 42n/2時，表示結(jié)點(diǎn)i為葉子結(jié)點(diǎn)。234561大根堆大根堆2345617有序列有序列T1=08, 25, 49, 46, 58, 67和序列和序列T2=91, 85, 76, 66, 58, 67, 55,判別它們能否判別它們能否 “堆？堆？小根堆小根堆小頂堆小頂堆 最小堆最小堆大頂堆大頂堆最

3、大堆最大堆123456例：關(guān)鍵字序列例：關(guān)鍵字序列T= (21，25，49，25*，16，08，請建大根堆。，請建大根堆。解：為便于了解，先將原始序列畫成完全二叉樹的方式：解：為便于了解，先將原始序列畫成完全二叉樹的方式：注：終端結(jié)點(diǎn)即葉子沒有任何子女，無需單獨(dú)調(diào)整。注：終端結(jié)點(diǎn)即葉子沒有任何子女，無需單獨(dú)調(diào)整。而且而且21還該當(dāng)向下比較！還該當(dāng)向下比較！1234561365421234561365421234561365421234561365421234561365429.5 9.5 歸并排序歸并排序9.6 9.6 基數(shù)排序基數(shù)排序 (Radix Sort)(Radix Sort)以上兩例

4、都是典型的多關(guān)鍵字排序！由于有分組，故此算法需遞歸實(shí)現(xiàn)。例：初始關(guān)鍵字序列例：初始關(guān)鍵字序列T=32, 13, 27, 32*, 19，33，請分別，請分別用用MSD和和LSD進(jìn)展排序，并討論其優(yōu)缺陷。進(jìn)展排序，并討論其優(yōu)缺陷。法法1MSD：原始序列：原始序列：32, 13, 27, 32*, 19， 33 先按高位先按高位Ki1 排序：排序：13, 19, 27, 32, 32*，33 再按低位再按低位Ki2 排序排序 ： 13, 19 ， 27, 32, 32*, 33法法2LSD： 原始序列：原始序列： 32, 13, 27, 32*, 19 ，33 先按低位先按低位Ki2排序：排序：

5、32, 32*, 13, 33, 27, 19 再按高位再按高位Ki1排序：排序： 13, 19 , 27, 32, 32*, 33無需分組，易編程實(shí)現(xiàn)！11552164547077027755645402112170775554，6421，117002又稱散列過程！又稱散列過程！775564540211217070，776454，552111027770645554211102e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9r05307909211016144852

60e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9530790921101614485215306637738530790921101614485215306637738r0r0530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f953079092110161448

7、5215306637738r0r0各種內(nèi)部排序方法的比較各種內(nèi)部排序方法的比較 (教材教材P289簡單排序簡單排序 O(n)O(n2) O(n2) O(1） 穩(wěn)定穩(wěn)定 快速排序快速排序O(nlgn )O(nlgn) O(n2) O(lgn) 不穩(wěn)定不穩(wěn)定 堆排序堆排序 O(nlgn )O(nlgn ) O(nlgn) O(1）不穩(wěn)定不穩(wěn)定 歸并排序歸并排序 O(nlgn ) O(nlgn ) O(nlgn) O(n）穩(wěn)定穩(wěn)定基數(shù)排序基數(shù)排序O(d(n+rd) O(d(n+rd) O(d(n+rd) O(rd)穩(wěn)定穩(wěn)定 簡單選擇簡單選擇 O(n2) O(n2) O(n2) O(1） 不穩(wěn)定不穩(wěn)定 直接插入直接插入 O(n) O(n2) O(n2) O(1）穩(wěn)定穩(wěn)定 折半插入折半插入O(nlgn )O(nlgn )O(nlgn )O(1）穩(wěn)定穩(wěn)定冒泡冒泡 O(n) O(n2) O(n2) O(1）穩(wěn)定穩(wěn)定 討論：假設(shè)初始記錄根本無序，那么選用哪些排序討論：假設(shè)初始記錄根本無序，那么選用哪些排序方法比較適宜？假設(shè)初始記錄根本無序，那么最好方法比較適宜？假設(shè)初始記錄根本無序，那么最好選用哪些排序方法？選用哪些排序方法？答：對根本有序的情況，可選用堆