軟件技術(shù)基礎(chǔ)課件4-數(shù)據(jù)結(jié)構(gòu)與算法3

部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)表達(dá)一種非線性邏輯關(guān)系具有“頂點(diǎn)”和“頂點(diǎn)之間關(guān)系”兩類要素：頂點(diǎn)的前驅(qū)和后繼數(shù)目無(wú)限制頂點(diǎn)之間關(guān)系是任意的任意2頂點(diǎn)之間均可能直接或間接關(guān)聯(lián)應(yīng)用場(chǎng)合——非常廣泛：邏輯推理戰(zhàn)場(chǎng)支援體系產(chǎn)品裝配活動(dòng)

預(yù)警機(jī)

偵察機(jī)

戰(zhàn)斗機(jī)

地面雷達(dá)SEAD飛機(jī)

通信衛(wèi)星

電子干擾機(jī)

導(dǎo)航衛(wèi)星1第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)定義：一種復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系（也稱弧或邊）集合組成?？梢员硎緸椋?/p>

G＝(V,{<VR>})

其中：

V

是頂點(diǎn)的有窮非空集合；

<VR>是頂點(diǎn)之間關(guān)系的有窮集合，也叫做弧或邊集合。

弧是頂點(diǎn)的有序?qū)?，邊是頂點(diǎn)的無(wú)序?qū)Α?第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本術(shù)語(yǔ)：有向圖無(wú)向圖

頂點(diǎn)：圖中的數(shù)據(jù)元素。

v2v1v3v4G1v2v1v3v4v5G2

?。喝?lt;v,w>∈VR，則<v,w>表示從v到w的一條弧，且稱v

為弧尾，稱w

為弧頭，此時(shí)的圖稱為有向圖。

G1=(V1,{A1})V1={v1,v2,v3,v4}

A1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}

邊：若<v,w>∈VR必有<w,v>∈VR，則以無(wú)序?qū)?v,w)代表這兩個(gè)有序?qū)?，表示v和w之間的一條邊，此時(shí)的圖稱為無(wú)向圖。

G2=(V2,{E2})V2={v1,v2,v3,v4,v5}

E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}3第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本術(shù)語(yǔ)：

無(wú)向圖中邊的取值范圍：0≤e≤n(n-1)/2。（用n表示圖中頂點(diǎn)數(shù)目，用e

表示邊的數(shù)目。且不考慮頂點(diǎn)到其自身的邊。）

完全圖：有

n(n-1)/2條邊的無(wú)向圖（即：無(wú)向圖中每?jī)蓚€(gè)頂點(diǎn)之間都存在著一條邊)稱為完全圖。

有向完全圖：有

n(n-1)條弧的有向圖（即：有向圖中每?jī)蓚€(gè)頂點(diǎn)之間都存在著方向相反的兩條?。┓Q為有向完全圖。v2v1v3v4v5

有向圖中弧的取值范圍：0≤e≤n(n-1)。（用n表示圖中頂點(diǎn)數(shù)目，用e

表示弧的數(shù)目。且不考慮頂點(diǎn)到其自身的弧。）

v2v1v3v44第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本術(shù)語(yǔ)：

稀疏圖：含有很少條邊或弧的圖。

稠密圖：含有很多條邊或弧的接近完全圖的圖。

權(quán)：與圖的邊或弧相關(guān)的數(shù)，這些數(shù)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。

網(wǎng)：邊或弧帶有權(quán)值的圖。北京國(guó)際上海虹橋570675虹橋機(jī)場(chǎng)交大徐匯19.055第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本術(shù)語(yǔ)：v3v4v5

子圖：如果圖

G=(V,{E})和

G′=(V

′,{E′})，滿足：V

′V且E′E，則稱G′為G

的子圖。v2v1v3v4v2v1v3v4v5v1v1v3v2v1v4v2v1v5v2v1v4v5v2v1v5

鄰接點(diǎn)：若(v,v′)是一條邊，則稱頂點(diǎn)v和v′互為鄰接點(diǎn)，或稱v和v′相鄰接；稱邊(v,v′)依附于頂點(diǎn)v

和v′，或稱(v,v′)與頂點(diǎn)v

和v′相關(guān)聯(lián)。

若<v,v′>是一條弧，則稱頂點(diǎn)v

鄰接到

v′，頂點(diǎn)v′鄰接自頂點(diǎn)v。并稱弧

<v,v′>與頂點(diǎn)v

和v′相關(guān)聯(lián)。v2v1v4第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本術(shù)語(yǔ)：

度：無(wú)向圖中頂點(diǎn)v

的度是和v

相關(guān)聯(lián)的邊的數(shù)目，記為：TD(v)。v2v1v3v4v5

入度：有向圖中以頂點(diǎn)v

為頭的弧的數(shù)目稱為v

的入度，記為：ID(v)。

出度：有向圖中以頂點(diǎn)v

為尾的弧的數(shù)目稱為v

的出度，記為：OD(v)。

度：入度和出度之和，即：TD(v)=ID(v)+OD(v)。v2v1v3v4

如果頂點(diǎn)vi

的度為T(mén)D(vi)，則一個(gè)有n

個(gè)頂點(diǎn)

E條邊（?。┑膱D，滿足如下關(guān)系：第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本術(shù)語(yǔ)：

路徑：從頂點(diǎn)v

到v′的路徑是一個(gè)頂點(diǎn)序列(v=vi,0,vi,1,…,vi,m=v′)，滿足

(vi,j-1,vi,j)VR

或<vi,j-1,vi,j>VR，(1jm)。對(duì)于有向圖，路徑也是有向的。

v2v1v3v4v5v2v1v3v4

路徑長(zhǎng)度：路徑上邊或弧的數(shù)目。

回路（環(huán)）：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。

簡(jiǎn)單路徑：序列中頂點(diǎn)（兩端點(diǎn)除外）不重復(fù)出現(xiàn)的路徑。

簡(jiǎn)單回路（簡(jiǎn)單環(huán)）：前后兩端點(diǎn)相同的簡(jiǎn)單路徑。

連通：從頂點(diǎn)v

到

v′有路徑，則說(shuō)

v

和

v′是連通的。

連通圖：圖中任意兩個(gè)頂點(diǎn)都是連通的。

v2v1v3v4v5

非連通圖：有n

個(gè)頂點(diǎn)和小于n-1條邊的圖。第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本術(shù)語(yǔ)：

連通分量：無(wú)向圖的極大連通子圖（不存在包含它的更大的連通子圖）；任何連通圖的連通分量只有一個(gè)，即其本身；非連通圖有多個(gè)連通分量（非連通圖的每一個(gè)連通部分）。v2v1v3v4v5v2v1v3v4v5

強(qiáng)連通圖：任意兩個(gè)頂點(diǎn)都連通的有向圖。v2v1v3v4

強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖；任何強(qiáng)連通圖的強(qiáng)連通分量只有一個(gè)，即其本身；非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。v2v1v3v4v2v1v3v4第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本術(shù)語(yǔ)：

生成樹(shù)：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖。v2v1v3v4v5v2v1v3v4v5v2v1v3v4v5v2v1v3v4v5性質(zhì)：一個(gè)圖可以有許多棵不同的生成樹(shù)所有生成樹(shù)具有以下共同特點(diǎn)：

生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同；生成樹(shù)是圖的極小連通子圖；一個(gè)有n

個(gè)頂點(diǎn)的連通圖的生成樹(shù)有

n-1條邊；

生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的；

在生成樹(shù)中再加一條邊必然形成回路。

含n

個(gè)頂點(diǎn)

n-1條邊的圖不一定是生成樹(shù)。

v2v1v3v4v5第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本術(shù)語(yǔ)：

生成森林：對(duì)于非連通圖，其每個(gè)連通分量可以構(gòu)造一棵生成樹(shù)，合成起來(lái)就是一個(gè)生成森林。

有向樹(shù)：如果一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0，其余頂點(diǎn)的入度均為1，則是一棵有向樹(shù)。

有向圖的生成森林：由若干棵有向樹(shù)組成，含有圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹(shù)的弧。B

A

CF

ED

B

A

DF

EC

第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：1、多重鏈表法v1v2^^v4^v3^^v1

v2

v4^

v5^

v3v2v1v3v4G1v2v1v3v4v5G2第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：2、鄰接矩陣法（數(shù)組存儲(chǔ)）

對(duì)于一個(gè)具有n

個(gè)頂點(diǎn)的圖，可用兩個(gè)數(shù)組存儲(chǔ)。其中一個(gè)一維數(shù)組存儲(chǔ)數(shù)據(jù)元素（頂點(diǎn)）的信息，另一個(gè)二維數(shù)組（圖的鄰接矩陣）存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系（邊或?。┑男畔?。

鄰接矩陣：設(shè)G=(V,{VR})是具有n

個(gè)頂點(diǎn)的圖，頂點(diǎn)的順序依次為

{v1,v2,…,vn}，則G的鄰接矩陣是具有如下性質(zhì)的n

階方陣：

第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)v2v1v3v4G1v2v1v3v4v5G2v1

v2

v3

v4

v1

v2v3v4v1

v2v3v4v5基本性質(zhì)：

無(wú)向圖的鄰接矩陣對(duì)稱，可壓縮存儲(chǔ)；有n

個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為

n(n-1)/2。

有向圖鄰接矩陣不一定對(duì)稱；有

n

個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間

為

n2，空間復(fù)雜度為O(n2)，用于稀疏圖時(shí)空間浪費(fèi)嚴(yán)重。

無(wú)向圖中頂點(diǎn)

vi

的度

TD(vi)是鄰接矩陣中第

i

行

1的個(gè)數(shù)。

有向圖中

頂點(diǎn)

vi

的出度是鄰接矩陣中第

i

行

1的個(gè)數(shù)。頂點(diǎn)

vi

的入度是鄰接矩陣中第

i

列

1的個(gè)數(shù)。第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)網(wǎng)的鄰接矩陣：

v2v1v3v4v5v65489755613v1

v2

v3

v4

v5v6v1

v2v3v4v5v6第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：3、鄰接表法頭結(jié)點(diǎn)datafirstarc表結(jié)點(diǎn)adjvexnextarcinfov2v1v3v4v5G2v1v3v4v2v5012343^142^043^12^02^1鏈域，指示下一條邊或弧。

特點(diǎn)：

若無(wú)向圖中有n

個(gè)頂點(diǎn)、e

條邊，則其鄰接表需n

個(gè)頭結(jié)點(diǎn)和2e

個(gè)表結(jié)點(diǎn)。適宜存儲(chǔ)稀疏圖。

無(wú)向圖中頂點(diǎn)vi

的度為第i

個(gè)單鏈表中的結(jié)點(diǎn)數(shù)。

鄰接點(diǎn)域，存放與

vi

鄰接的頂點(diǎn)在表頭數(shù)組中的位置。

第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)有向圖的鄰接表：

v2v1v3v4G101232^13^^0v1v3v4v2^0123^30^^2v1v3v4v2^0鄰接表逆鄰接表

頂點(diǎn)vi

的出度為第i

個(gè)單鏈

表中的結(jié)點(diǎn)個(gè)數(shù)。

特點(diǎn)：

頂點(diǎn)vi的入度為整個(gè)單鏈表

中鄰接點(diǎn)域值是

i-1的結(jié)點(diǎn)

個(gè)數(shù)。找出度易，找入度難。找入度易，找出度難。

頂點(diǎn)vi

的入度為第i

個(gè)單鏈

表中的結(jié)點(diǎn)個(gè)數(shù)。

頂點(diǎn)vi的出度為整個(gè)單鏈表

中鄰接點(diǎn)域值是

i-1的結(jié)點(diǎn)

個(gè)數(shù)。第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本操作類型：構(gòu)造圖結(jié)構(gòu)銷毀圖結(jié)構(gòu)訪問(wèn)頂點(diǎn)：獲取頂點(diǎn)位置、獲取頂點(diǎn)數(shù)值、獲取頂點(diǎn)的鄰接點(diǎn)頂點(diǎn)賦值插入頂點(diǎn)刪除頂點(diǎn)添加邊或弧刪除邊或弧遍歷頂點(diǎn)：深度優(yōu)先、廣度優(yōu)先

……

18第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)基本操作——遍歷：從圖的任意指定頂點(diǎn)出發(fā)，依照某種規(guī)則去訪問(wèn)圖中所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次，這一過(guò)程叫做圖的遍歷。按照深度優(yōu)先和廣度優(yōu)先規(guī)則：深度優(yōu)先遍歷法（Depth_FirstSearch——DFS）廣度優(yōu)先遍歷法（Breadth_FristSearch——BFS）V1V2V4V5V3V7V6V8第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)圖的深度優(yōu)先遍歷（DFS）——與樹(shù)的“先序遍歷”類似方法：1、訪問(wèn)指定的起始頂點(diǎn)；

2、若當(dāng)前訪問(wèn)的頂點(diǎn)的鄰接頂點(diǎn)有未被訪問(wèn)的，則任選一個(gè)訪問(wèn)之；反之，退回到最近訪問(wèn)過(guò)的頂點(diǎn)；直到與起始頂點(diǎn)相通的全部頂點(diǎn)都訪問(wèn)完畢；

3、若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則再選其中一個(gè)頂點(diǎn)

作為起始頂點(diǎn)并訪問(wèn)之，轉(zhuǎn)

2；反之，遍歷結(jié)束。例：

V1頂點(diǎn)訪問(wèn)次序：V2V4V8V5V3V6V7

V1V2V5V8V4V3V6V7

V1V2V4V8V5V3V7V6

V1V2V5V8V4V3V7V6

V1V3V6V7V2V4V8V5

V1V2V4V5V3V7V6V8注：通常為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問(wèn)標(biāo)志”，以解決鄰接頂點(diǎn)是否已經(jīng)訪問(wèn)問(wèn)題。第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)

1370V1V2V4V8V5V301234567^^V1V2V3V4V5V6V7V82^13^156^7^7^6^00000000012345672V65V76V1V2V4V5V3V7V6V8411111111有向圖深度優(yōu)先遍歷舉例：第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)圖的廣度優(yōu)先遍歷（BFS）例：

頂點(diǎn)訪問(wèn)次序：V1V2V4V5V3V7V6V8注：通常為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問(wèn)標(biāo)志”，以解決鄰接頂點(diǎn)是否已經(jīng)訪問(wèn)問(wèn)題。

方法：從圖的某一結(jié)點(diǎn)出發(fā)，首先依次訪問(wèn)該結(jié)點(diǎn)的所有鄰接頂點(diǎn)Vi1,Vi2,…,Vin

再按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)與它們相鄰接的所有未被訪問(wèn)的頂點(diǎn)，重復(fù)此過(guò)程，直至所有頂點(diǎn)均被訪問(wèn)為止。V1V2V3V4V5V6V7V8

V1V3V2V7V6V5V4V8

V1V2V3V5V4V7V6V8

第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)圖應(yīng)用舉例——裝配活動(dòng)建模第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)鄰接矩陣表達(dá)：第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖（Graph）結(jié)構(gòu)第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖結(jié)構(gòu)習(xí)題：1、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和與所有邊數(shù)之間存在什么關(guān)系？2、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和與所有頂點(diǎn)的出度之和之間存在什么關(guān)系？3、一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有多少條邊？4、具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有多少條邊才能確保是一個(gè)連通圖？5、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則表頭數(shù)組的大小是多少？所有鄰接表中的結(jié)點(diǎn)總數(shù)是多少？第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法圖結(jié)構(gòu)習(xí)題：6、根據(jù)右圖，寫(xiě)出其鄰接矩陣表達(dá)式；并從v2出發(fā)按深度優(yōu)先搜索和廣度優(yōu)先搜索算法遍歷得到所有可能的頂點(diǎn)序列7、一個(gè)有向圖的鄰接表如右圖所示，畫(huà)出該圖的邏輯結(jié)構(gòu)，并求出根據(jù)深度優(yōu)先搜索算法從頂點(diǎn)v1出發(fā)遍歷得到的頂點(diǎn)序列第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序——其他算法的基礎(chǔ)之一主要內(nèi)容：1、插入排序（直接插入排序、折半插入排序、希爾排序）；2、交換排序（起泡排序、快速排序）；3、選擇排序（簡(jiǎn)單選擇排序）；

內(nèi)部排序和外部排序：若整個(gè)排序過(guò)程不需要訪問(wèn)外存便能完成，則稱此類排序問(wèn)題為內(nèi)部排序；若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過(guò)程不可能在內(nèi)存中完成，則稱此類排序問(wèn)題為外部排序。29第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序

定義：將數(shù)據(jù)元素的一個(gè)任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。例：將關(guān)鍵字序列：52,49,80,36,14,58,61,23調(diào)整為：14,23,36,49,52,58,61,80

按主關(guān)鍵字排序則結(jié)果惟一。按次關(guān)鍵字排序則結(jié)果可以不惟一（有相同關(guān)鍵字）

設(shè)Ki、Kj

(1≤i≤n,1≤j≤n,i≠j)分別為記錄Ri、Rj

的關(guān)鍵字，且Ki=Kj

，在排序前的序列中Ri

領(lǐng)先于Rj（即i<j）。若在排序后的序列中Ri

仍領(lǐng)先于Rj，則稱所用的排序方法穩(wěn)定；反之，則稱所用的排序方法不穩(wěn)定。例：設(shè)排序前的關(guān)鍵字序列為：52,49,80,36,14,58,36,23

若排序后的關(guān)鍵字序列為：14,23,36,36,49,52,58,80，則排序方法是穩(wěn)定的。若排序后的關(guān)鍵字序列為：14,23,36,36,49,52,58,80，則排序方法是不穩(wěn)定的。30第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序1、插入排序有序序列R[1..i-1]R[i]無(wú)序序列R[i..n]（1）一趟直接插入排序的基本思想：有序序列R[1..i]無(wú)序序列R[i+1..n]實(shí)現(xiàn)“一趟插入排序”可分三步進(jìn)行：3步．將R[i]插入（復(fù)制）到R[j+1]的位置上。2步．將R[j+1..i-1]中的所有記錄均后移一個(gè)位置；1步．在R[1..i-1]中查找R[i]的插入位置，

R[1..j].keyR[i].key<R[j+1..i-1].key；

排序過(guò)程：先將序列中第

1

個(gè)記錄看成是一個(gè)有序子序列，

然后從第

2

個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序。

31第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序比較次數(shù)和移動(dòng)次數(shù)均約為：T(n)=O(n2)時(shí)間復(fù)雜度：比較次數(shù)：移動(dòng)次數(shù)：0最好的情況：待排序記錄按關(guān)鍵字從小到大排列（正序）比較次數(shù)：移動(dòng)次數(shù)：最壞的情況：待排序記錄按關(guān)鍵字從大到小排列（逆序）

一般情況：待排序記錄是隨機(jī)的，取平均值。

空間復(fù)雜度：S(n)=O(1)直接插入排序是穩(wěn)定排序54321第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序（2）折半插入排序：用折半查找方法確定插入位置的排序T(n)=O(n2)時(shí)間復(fù)雜度：空間復(fù)雜度：S(n)=O(1)穩(wěn)定性：折半插入排序是穩(wěn)定排序僅減少了比較次數(shù)，移動(dòng)次數(shù)不變。第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序（3）希爾排序：基本思想是對(duì)待排序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整第二趟希爾排序第三趟分組，設(shè)d3=1

排序過(guò)程：先取一個(gè)正整數(shù)d1<n，把所有相隔

d1

的記錄放

在一組內(nèi)，組內(nèi)進(jìn)行直接插入排序；然后取

d2<d1，重復(fù)上述分

組和排序操作；直至

di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹埂?/p>

其中

di

稱為增量。例：49386597761327495504第一趟希爾排序1327495504493865977613044938274955659776第三趟希爾排序第一趟分組，設(shè)d1=54938

6597761327

495504

13274955044938659776第二趟分組，設(shè)d2=304132738494955657697第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序希爾排序特點(diǎn)：

分組不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列。

增量序列取法希爾最早提出的選法是d1=n/2，di+1=di/2?？伺?Knuth)提出的選法是di+1=(di-1)

/3。還有其他不同的取法。。

1)、沒(méi)有除1以外的公因子；

2)、最后一個(gè)增量值必須為1。

希爾排序可提高排序速度

1)、記錄跳躍式前移，在進(jìn)行最后一趟排序時(shí)，已基本有序。

2)、分組后n

值減小，n2更小，而

T(n)=O(n2)，所以

T(n)從

總體上看是減小了。

第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序1、交換排序

（1）冒泡法3、重復(fù)直到

“在一趟排序

過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操

作”或“僅第一二個(gè)交換過(guò)”為止。

1、比較第一個(gè)記錄與第二個(gè)記錄，若關(guān)鍵字為逆序則交換；然

后比較第二個(gè)記錄與第三個(gè)記錄；

依次類推，直至第

n-1個(gè)記錄和第

n

個(gè)記錄比較為止——第一趟冒泡

排序，結(jié)果關(guān)鍵字最大的記錄被安

置在最后一個(gè)記錄上。

2、對(duì)前

n-1個(gè)記錄進(jìn)行第二

趟冒泡排序，結(jié)果使關(guān)鍵字次大的

記錄被安置在第

n-1個(gè)記錄位置。

初始關(guān)鍵字第一趟排序979727384965761327499738496513274976第二趟排序384913274965第三趟排序3813274949

第四趟排序13273849第五趟排序132738第六趟排序4938659776132749第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序

時(shí)間復(fù)雜度：

最好情況（正序）比較次數(shù)：n-1移動(dòng)次數(shù)：0

T(n)=O(n)

最壞情況（逆序）比較次數(shù)：移動(dòng)次數(shù)：

T(n)=O(n2)

空間復(fù)雜度：S(n)=O(1)

穩(wěn)定性：穩(wěn)定排序第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序s一般取第一個(gè)記錄

基本思想：任選一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡關(guān)鍵字小于樞軸的記錄均移至樞軸之前，凡關(guān)鍵字大于樞軸的記錄均移至樞軸之后。（2）一趟快速排序（一次劃分）lowhigh設(shè)R[s]=52為樞軸。例：

5252498036145861972375t

附設(shè)兩個(gè)指針low和high，從high所指位置起向前搜索找到第一個(gè)關(guān)鍵字小于樞軸的關(guān)鍵字的記錄與樞軸記錄交換，然后從low+1所指位置起向后搜索找到第一個(gè)關(guān)鍵字大于樞軸的關(guān)鍵字的記錄與樞軸記錄交換，重復(fù)這兩步直至low=high為止。high23lowlow80highhighhighhigh14lowlow52第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法排序（3）快速排序——首先對(duì)無(wú)序的記錄序列進(jìn)行“一次劃分”，之后分別對(duì)分割所得兩個(gè)子序列“遞歸”進(jìn)行一趟快速排序快速排序過(guò)程無(wú)序的記錄序列無(wú)序記錄子序列(1)無(wú)序子序列(2)