計(jì)算機(jī)課件第八章 排序

排序的定義

排序的功能是將一個(gè)數(shù)據(jù)元素（記錄）的任

意序列，重新排列成一個(gè)按關(guān)鍵字有序的

序列。

★￥

*

2

排序的分類

?按待排序記錄所在位置

內(nèi)部排序：待排序記錄存放在內(nèi)存

夕卜部排序：排序過程中需對外存進(jìn)行訪問的

排序

?按排序依據(jù)原則

插入排序：直接插入排序、折半插入排序、

希爾排序

交換排序：冒泡排序、快速排序

選擇排序：前單選擇排序、堆排序去.

歸并排序：2-路歸并排序★

3

排序的基本操作

?比較兩個(gè)關(guān)鍵字大小

將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置

★￥

*

4

排序?qū)ο蟮臄?shù)據(jù)類型

定義待排序的記錄的數(shù)據(jù)類型為:

typedefstruct

{intkey;

elemtypedata;

}redtype;

redtyper[n];

★￥

5

插入排序

基本思想：每步將一個(gè)待排序的記錄，按其

關(guān)鍵字值的大小插入到前面已經(jīng)排序的文件

中適當(dāng)?shù)奈恢蒙?，直到全部插完為止?/p>

★?

3

★

插入排序直接插入排序

例i=l(49386597761327比較次數(shù)移動(dòng)次數(shù)

____I

i=238(3849)659776132721

i=3(384965)9776132710

i=4(38496597)76132710

i=5(3849657697)132721.

i=6(133849657697)彳765

i=7(132738496576976

jj'Jj'j'j'

排序結(jié)果：(13273849657697)

8

直接插入排序算法算法8.Ltxt

(1)設(shè)置監(jiān)視哨r[0],將待插入記錄的

值賦給r[0];

(2)設(shè)置開始查找的位置j;

(3)在數(shù)組中進(jìn)行搜索，搜索中將第j個(gè)

記錄后移，直至r[0].key>r[j].key為止

(4)將r[0]插入在r[j+l]的位置上

■

9

直接插入排序算法分析

按平均比較次數(shù)計(jì)算，將n個(gè)記錄進(jìn)行直接插入排序所

需的平均比較次數(shù)為：

n2

i(H+2)(H-1)“2+〃一2n

Sin——

i=2乙444

直接插入排序的時(shí)間復(fù)雜度為2

0(n)o

空間復(fù)雜度為0(1)

★￥

直接插入排序是一種穩(wěn)定的排序方法。

★

10

插入排序希爾排序

希爾排序的作法是：選定第一個(gè)增量

dl<n,把全部記錄按此值從第一個(gè)記錄

起進(jìn)行分組，所有相距為dl的記錄作為

一組，先在各組內(nèi)進(jìn)行插入排序，然后

減小間隔，取第二個(gè)增量d2〈dl,重復(fù)上

述分組和排序過程，直至增量值di=l為

止，即所有的記錄放在同一組內(nèi)排序。

■

11

例初始：4938659776132748554

取dl=5

—分2目;4。a父6s。77A14974554

一趟排序：5549776

取d2=3

二趟分組：〔1I7,

二趟排序：

取d3=l

三趟分組：1327485544938659776

1―：；

三趟排序：4132738484955657697/

12

匐

插入排序希爾排序算法算法8.2.txt

1）外循環(huán)以各種不同的間隔距離d進(jìn)行排序，直

到d==l為止；

2）第二重循環(huán)是在某一個(gè)d值下對各組進(jìn)行排序，

若在某個(gè)d值下發(fā)生了記錄的交換，則需繼續(xù)

第三重循環(huán)循環(huán)，直至各組內(nèi)均無記錄的交換

為止。即各組內(nèi)已完成排序任務(wù);

3）第三重循環(huán)是從第一個(gè)記錄開始，按某個(gè)d值

為間距進(jìn)行組內(nèi)比較。若有逆序，則進(jìn)行交換。

★★

■

13

希爾排序筍法分析

主要特點(diǎn)是每一趟以不同的增量進(jìn)行插入

排序。當(dāng)d較大時(shí)，被移動(dòng)的記錄是跳躍

式進(jìn)行的。到最后一趟排序時(shí)(d=l),許

多記錄已經(jīng)有序，不需要多少移動(dòng)，所以

能提高了排序的速度。

希爾排序是不穩(wěn)定的排序方法。

JT14

交換排序

交換排序是通過兩兩比較待排序記錄的

關(guān)鍵值，交換不滿足順序的那些偶對，直到

全部滿足為止。

★￥

15

*

交換排序

算法&3.txt

1.將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)

鍵字進(jìn)行比較，若為逆序

r[1].key>r[2].key,則交換；然后比較第

二個(gè)記錄與第三個(gè)記錄；依次類推，直至

第nT個(gè)記錄和第n個(gè)記錄比較為止-----第

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

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

2.對前nT個(gè)記錄進(jìn)行第二趟冒泡排序★約臀

使關(guān)鍵字次大的記錄被安置在軍T個(gè)記錄

位置。

交換排序

38

例3838383313

1327

4949492727

U

65653030

2730第

761338六

3038第

27

趟

五

13274949第

30

趟

2730四

65第

65

趟

3076二

76第

趟

97初

97第

二

一

始

趟

趟

關(guān)

鍵

字

7

冒泡排序算法分析

由上述算法可見，當(dāng)初始序列中記錄已按關(guān)

鍵字次序排好序，則只需要進(jìn)行一趟排序，

在排序過程中只需要進(jìn)行nT次比較，記錄移

動(dòng)次數(shù)為0；反之，若初始序列中記錄按逆序

排列，若待排序的序列有n個(gè)記錄，最多進(jìn)行

nT趟排序，最大比較次數(shù)為

n—\n(n—1)n2

zs—)=-----x--

i=l22

交換記錄時(shí)移動(dòng)記錄的次數(shù)也約為3n2/2次，故費(fèi),

的時(shí)間復(fù)雜度為0(/)o冒泡排序是穩(wěn)定的小牛

18

對r[s...中記錄進(jìn)行一趟快速相、序,附設(shè)兩

個(gè)指針i和j,設(shè)樞軸記錄rp=r[s],x=rp.key

?初始時(shí)令i=s,j=t

?首先從j所指位置向前搜索第一個(gè)關(guān)鍵

字小于x的記錄，并和rp交換

?再從i所指位置起向后搜索，找到第一

個(gè)關(guān)鍵字大于x的記錄，和rp交換

?重復(fù)上述兩步，直至i=j為止

?再分別對兩個(gè)子序列進(jìn)行快速排好，*

直到每個(gè)子序列只含有一個(gè)記軍為止

20

X

11

初始關(guān)鍵字:2738134976976550

tT

ftt?*tt

ii1項(xiàng)jJJj

完成一趟排序：(273813)49(76976550)

分別進(jìn)行快速排序：(13)38)49(5065)76(97)

快速排序結(jié)束：1338495065

21

4.txt

1)確定第一個(gè)記錄為基準(zhǔn)記錄中],先從j所指示的位

置起向前掃描，當(dāng)中].key>r[j].key時(shí)，交換中].key

和r5.key,使關(guān)鍵字值比基準(zhǔn)記錄的關(guān)鍵字值小的

記錄交琉到前面；

2)從i所指示的位置起向后掃描，直到r[t].key〈r[i].key,

交換巾].key和r[i].key,使關(guān)鍵字值比基準(zhǔn)記錄的關(guān)

鍵字值大的記錄交換到后面；

3)重復(fù)（1）和（2）,直至i=j為止完成一趟排序；

4)只要t<w,重復(fù)（1）至（3）分別對基準(zhǔn)記錄兩邊

的部分進(jìn)行排序。

■

22

快速排序的排序算法分析

快速排序平均時(shí)間復(fù)雜度為

0(nlog2n)o

最壞情況下時(shí)間復(fù)雜度為0(n2),快速排序所

需的比較次數(shù)反而最多。

快速排序法不穩(wěn)定。

快速排序需要一個(gè)?？臻g來實(shí)現(xiàn)遞歸。棧的

最大深度為所需棧空間為

Llog2nJ+1,

最壞情況下，遞歸深度為所需

0(log2n)on,

棧空間為0(n)。去、

23

選擇排序是指每次從待排序的記錄中

選出關(guān)鍵字值最小（或最大）的記錄，順

序放在已排序的有序序列中，直到全部排

完。選擇排序主要包括簡單選擇排序和堆

排序兩種。

■

24

選擇排序-----簡單選擇排序

?首先通過nT次關(guān)鍵字比較，從

n個(gè)記錄中找出關(guān)鍵字最小的記錄，

將它與第一個(gè)記錄交換

?再通過n-2次比較，從剩余的n-

1個(gè)記錄中找出關(guān)鍵字次小的記錄，

將它與第二個(gè)記錄交換

?重復(fù)上述操作，共進(jìn)行nT趟排

序后，排序結(jié)束

★￥

■

25

kkk

III

例i=1初始：13865977649271

kk

1I

i=2一趟：[276597764938]

ttttI

jjjjj

二趟：97764938]

三趟:13

四趟:13

五趟:13

六趟:13

排序結(jié)束:13

26

簡單選擇排序算法5.txt

(1)查找待排序序列中最小的記錄，并將它

和該區(qū)間第一個(gè)記錄交換；

(2)重復(fù)(1)到第nT次排序后結(jié)束

★￥

*

27

簡單選擇排序算法分析

簡單選擇排序所需要的總的比較次

數(shù)為當(dāng)初始文件是有序時(shí)，最

0(4)o

小移動(dòng)記錄次數(shù)等于0,而當(dāng)初始文件

是逆序時(shí)，每次都要交換記錄。

直接選擇排序是不穩(wěn)定的.

■

28

選擇排序-----堆排序的引入

堆排序是簡單選擇排序的改進(jìn)。用直接

選擇排序從n個(gè)記錄中選出關(guān)鍵字值最小的

記錄要做nT次比較，然后從其余nT個(gè)記錄

中選出最小者要作n-2次比較。顯然，相鄰

兩趟中某些比較是重復(fù)的。為了避免重復(fù)比

較，可以采用樹形選擇排序比較。

29

堆排序的引入

樹形選擇排序總的比較次數(shù)為0(nlog2n),

與直接選擇排序比較，減少了比較次數(shù)，

但需要增加額外的存儲空間存放中間比較

結(jié)果和排序結(jié)果。

31

堆的定義

n個(gè)元素的序列（kl,k2,kn）,當(dāng)且僅當(dāng)滿足下

列關(guān)系時(shí),稱之為堆

'ki<k2i'ki>k2i

或(i=l,2,……Ln/2j)

.ki<k2i+l、ki2k2i+l

、例(13,38,27,50,76,65,49,97)

例(96,83,27,38,11,9)l7J

可將堆序列看成完全二叉樹，則堆頂

元素（完全二叉樹的根）必為序列中

n個(gè)元素的最小值或最大值32

堆排序的基本思路

堆排序的基本思路：對一組待排序的記

錄序列，先將其關(guān)鍵字按堆的定義排列一個(gè)

序列（稱初建堆），找到了最?。ㄗ畲螅╆P(guān)

鍵字，將其取出。用剩余的nT個(gè)元素再重建

堆，便可得到次?。ù未螅┲怠Ｈ绱朔磸?fù)執(zhí)

行，直到全部關(guān)鍵字排好序?yàn)橹埂?/p>

■

33

7697

紗u—

5049382750493827

1313

輸出：132738495065輸出：13273849506576

97.

76,65

50493827

13

輸出：1327384950657697★4

36

堆排序的關(guān)鍵問題

堆排序需解決的兩個(gè)問題：

?如何由一個(gè)無序序列建成一個(gè)堆？

?如何在輸出堆頂元素之后，調(diào)整剩

余元素，使之成為一個(gè)新的堆？

37

堆排序的關(guān)鍵問題

第二個(gè)問題解決方法—篩選算法8.6.txt

方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替

代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)

行比較，并與其中小者進(jìn)行交換；重復(fù)上述操作，

直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉

子的調(diào)整過程為“篩選”。

?第一個(gè)問題解決方法—建堆

方法：從無序序列的第Ln/2」個(gè)元素（即此無序序列

對應(yīng)的完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)）起,」至/

第一個(gè)元素止，進(jìn)行反復(fù)篩選?！铮?/p>

38

堆排序的算法及分析算法8.7.txt

堆排序只需要一個(gè)記錄大小的輔助空間o

堆排序算法的時(shí)間復(fù)雜度為0(nlogn)o

堆排序是一種不穩(wěn)定的排序方法。

■

40

歸并我E序

歸并排序：把兩個(gè)或多個(gè)有序表進(jìn)行合

并，得到一個(gè)新的有序表。將兩個(gè)有序子文

件合并成一個(gè)有序文件，稱為二路歸并。

*

41

2一路歸并排序過程

?設(shè)初始序列含有n個(gè)記錄，則可看成n個(gè)有

序的子序列，每個(gè)子序列長度為1

兩兩合并，得到［n/2」個(gè)長度為2或1的有序

子序列

再兩兩合并,如此重復(fù)，直至

得到一個(gè)長度為n的有序序列為止

■

42

2一路歸并排序過程

例初始關(guān)鍵字:

一趟歸并后:

二趟歸并后：

三趟歸并后:

43

2-路歸并排序的關(guān)鍵問題

合并是歸并排序的核心，即將兩個(gè)首

尾相連的有序子表合并成一個(gè)有序子

表。在合并的基礎(chǔ)上進(jìn)行一趟排序，

在一趟排序的基礎(chǔ)上完成多趟排序。

★

44

合并的算法算法8.8.txt.

1）設(shè)數(shù)組r中第一個(gè)有序子表從第h個(gè)記錄開始至第m個(gè)

記錄為止。即r[h]到r[m],第二個(gè)有序子表從第m+1

個(gè)記錄開始到第w個(gè)記皋為止，即r[m+l]到r[w],最

后形成的有序表為r[h]到r[w]；

2）設(shè)置I,j,k分別指向（1）中所指的三個(gè)有序表的第一

個(gè)單元。

3）比較巾]和山]的關(guān)鍵字值的大小，若巾].keySr|j].key,

則將第一個(gè)有序子表的記錄r國復(fù)制到數(shù)組a[k]中，并

使i++,k++;

4）否則，將第二個(gè)有序子表的記錄內(nèi)]復(fù)制到a[k]中]并

使j++,k++。依次類推，直到全部記錄復(fù)制到r[h]卻*

r[w]中。?

45

一趟歸并的算法算法8.9.txt.

把數(shù)組r中的長度為s的相鄰有序子表兩

兩合并，歸并成一個(gè)長度為2s的有序子

表，存于t數(shù)組中。

46

多趟合并的算法制去8.10.txt

思路是：第一趟有序子表長S為1,以后

每趟s加倍。第一趟將r數(shù)組進(jìn)行歸并后

存于t數(shù)組；第二趟將t數(shù)組歸并后存于

r數(shù)組；依次類推，若歸并的趟數(shù)為奇

數(shù)，需從t數(shù)組復(fù)制到r數(shù)組。

★

47

歸并排序算法分析

歸并排序的總的時(shí)間復(fù)雜度為0(nlog2n)。

歸并排序需要的附加存儲空間為0(n),所需

輔助空間較大。

二路歸并排序是穩(wěn)定的。

★￥

48

*基數(shù)排序

基數(shù)排序是和前面所述的各種排序方法完

全不同的一種排序方法。前面介紹的幾種排序

方法，都是根據(jù)關(guān)鍵字之間的比較和移動(dòng)記錄

來實(shí)現(xiàn)的，基數(shù)排序不需要進(jìn)行記錄關(guān)鍵字問

的比較，而是根據(jù)組成關(guān)鍵字的各位值，即借

助于多關(guān)鍵字排序的思想，用“分酉己”和“收

集”的方法進(jìn)行排序。

■

49

多關(guān)鍵字的排序

?假設(shè)有n個(gè)記錄的序列

?{RI,R2,Rn）

每個(gè)記錄Ri中含有d個(gè)關(guān)鍵字（Ki°,

Ki1,…，。廿1）,則稱上述記錄序列對關(guān)鍵

字（Ki°,Ki1,…，KidT）有序是指：對于序

列中任意兩個(gè)記錄Ri和Rj（l<i<j<n）都滿

足下列（詞典）有序關(guān)系：

?（Ki°,Ki<…，Ki="（叼0,Kj<…，叼匕

其中K°被稱為“最主”位關(guān)鍵字，KdT被稱牛

為“最次”位關(guān)鍵字?！?/p>

50

實(shí)現(xiàn)多關(guān)鍵字排序通常有兩種作法:

最高位優(yōu)先MSD法：失對K0進(jìn)行排序，并按K0的

不同值將記錄序列分成若干子序列之后，分別

對K1進(jìn)行排序，…，依次類推，直至最后對最

次位關(guān)鍵字排序完成為止。

最低位優(yōu)先LSD法：先對KdT進(jìn)行排序，然后對

Kd-2進(jìn)行排序，依次類推，直至對最主位關(guān)鍵

字K0排序完成為止。排序過程中不需要根據(jù)

“前一個(gè)，，關(guān)鍵字的排序結(jié)果，將記錄序列分

割成若干個(gè)（“前一個(gè)”關(guān)鍵字不同的）子序列。

★★

■

51

例如：學(xué)生記錄含三個(gè)關(guān)鍵字：系別、班號和班

內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。

LSD的排序過程如下：

無序序列1,2,152,3,182,1,20

對K2排序1,2,152,3/82,1,20

對K1排序2,1,201,2/52,3/8

對K0排序1,2,152,1,202,3,18

52

MSD法和LSD法的比較

比較MSD法和LSD法，一般來講，LSD

法要比MSD法來得簡單，因?yàn)長SD法是從

頭到尾進(jìn)行若干次分配和收集，執(zhí)行的

次數(shù)取決于構(gòu)成關(guān)鍵字值的成分為多少；

而MSD法則要處理各序列與子序列的獨(dú)

立排序問題，就可能復(fù)雜一些。

■

53

鏈?zhǔn)交鶖?shù)排序

假如多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的串值

范圍相同，則按LSD法進(jìn)行排序日寸，可以采用

“分配-收集”的方法，其好處是不需要進(jìn)行關(guān)

鍵字間的比較。

對于數(shù)字型或字符型的單關(guān)鍵字，可以看成是由

多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以

采用這種“分配-收集”的辦法進(jìn)行排序，稱作

基數(shù)排序法。

■

54

魚

鏈?zhǔn)交鶖?shù)排序籬去8.11.txt

在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，應(yīng)采用鏈表作存

儲結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序，具體作法為：

待排序記錄以指針相鏈，構(gòu)成一個(gè)鏈表；

“分配”時(shí)，按當(dāng)前“關(guān)鍵字位”所隼值，

將記錄分配到不同的“鏈隊(duì)列”中，每個(gè)隊(duì)

列中記錄的“關(guān)鍵字位”相同；

“收集”時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大

將各隊(duì)列首尾相鏈成一個(gè)鏈表；

對每個(gè)關(guān)鍵字位均重復(fù)2）和3）兩步。

■

55

鏈?zhǔn)交鶖?shù)排序

?例如：

p―369-367―167―239―237―138-230-139

?第一次分配得到

?f[0]—230-r[0]

?f⑺―367-167—237—r[7]

?f網(wǎng)一138-r[8]

?f[9]-369-239—139—r[9]

?第一次收集得到

p一230—367―167-237-138―368―239—139

■

56

?第二次分配得到

f[3]—230-237—138—239—139—r[3]

?f[6]-36，T167T368—r[6]一

?第二次收集得到

p一230T237Tl38-239—139T367Tl67-368

?第三次分配得到

?f[l]—138—139Tl67—r[l]

?f[2]->230—237—239—r[2]

?f[3]—367-368—r[3]

?第三次收集之后便得到記錄的有序序列

p-138—139Tl67-230—237T239—36726升

57

鏈?zhǔn)交鶖?shù)排序分析

鏈?zhǔn)交鶖?shù)的E序算法對數(shù)據(jù)進(jìn)行d趟掃描，每趟需

時(shí)間O(n+j)。因此總的計(jì)算時(shí)間為O(d(n+j))。對

于不同的基數(shù)j所用的時(shí)間是不同的。當(dāng)n較大或d

較小時(shí)，這種方法較為節(jié)省時(shí)間。

基數(shù)排序適用于鏈?zhǔn)酱鎯Y(jié)構(gòu)的記錄的排序，它要

求的附加存儲量是j個(gè)隊(duì)列的頭、是指針。所以，

需要0(n+j)輔助空間。

基數(shù)排序是一種穩(wěn)定的排序方法。

★￥

■

58

各種內(nèi)部排序方法性能比較

方法平均時(shí)間最壞情況輔助存儲

簡單排序O(n2)O(n2)0(1)

2

快速排序O(nlog2n)O(n)O(nlog2n)

堆排序O(nlog2n)O(nlog2n)0(1)

歸并排序O(nlog2n)O(nlog2n)O(n)

基數(shù)排序O(d(n+j))O(d(n+j))O((n+j)

■

59

各種內(nèi)部排序方法性能比較

1)從平均時(shí)間而言：快速排序最佳。但在最壞情況下時(shí)間性

能不如堆排序和歸并排序。

2)從算法簡單性看：由于直接選擇排序、直接插入排序和冒

泡排序的算法比較簡單，將其認(rèn)為是簡單算法，都包含在

上圖中的“簡單排序”中。對于希爾排序、堆排序、快速

排序和歸并排序算法，其算法比較復(fù)雜，認(rèn)為是復(fù)雜排序。

3)從穩(wěn)定性看：直接插入排序、冒泡排序和歸并排序是穩(wěn)定

的；而希爾排序、直接選擇排序、快速排序和堆排序是不

穩(wěn)定排序。

4)從待排序的記錄數(shù)n的大小看，n較小時(shí)，宜采用簡單排序；

而n較大時(shí)宜采用改進(jìn)排序?！顰

■

60

___________選擇排序的方法____________

(1)當(dāng)待排序記錄數(shù)n較大時(shí)，若要求排序穩(wěn)定，

則采用歸并排序。

(2)當(dāng)待排序記錄數(shù)n較大，關(guān)鍵字分布隨機(jī)，而

且不要求穩(wěn)定時(shí)，可采用快速排序；

(3)當(dāng)待排序記錄數(shù)n較大，關(guān)鍵字會出現(xiàn)正、逆

序情形，可采用堆排序(或歸并排序)。

(4)當(dāng)待排序記錄數(shù)n較小，記錄已接近有序或隨

機(jī)分布時(shí)，又要求排序穩(wěn)定，可采用直接插入排序。

(5)當(dāng)待排序記錄數(shù)n較小，且對穩(wěn)定性不作筮熱

時(shí)，可采用直接選擇排序?！?/p>

61

*夕卜部排序簡介

在實(shí)際問題中，經(jīng)常會遇到輸入文件中記錄的

數(shù)量很大，計(jì)算機(jī)的內(nèi)存不能容納時(shí)，排序過

程必須借助外部存儲器才能完成，這時(shí)的排序

就稱為外部排序。

★★

62

外存信息的存取磁帶

磁帶是涂上一層磁性材料的窄帶，磁帶

卷在帶盤上，帶盤安裝在磁帶驅(qū)動(dòng)器的

轉(zhuǎn)軸上。驅(qū)動(dòng)器控制磁帶盤轉(zhuǎn)動(dòng)，帶動(dòng)

磁帶移動(dòng)，通過讀/寫磁頭進(jìn)行讀/寫信

息的操作。

63

外有信息的存取磁盤

磁盤存隼信息時(shí)，首先要確定信息所在的柱面，

再將磁頭移動(dòng)到所需磁道