山東輕工業學院

教師授課教案

課程名稱：數據結構（計科）

課程代碼：0301306

學分：4.5

課程類別：必修

開課單位：信息科學與技術學院

授課班級:

授課教師：楊春花

山東輕工業學院教務處制

年

第

月

星期

節

日

年

第

星期

月

節

日

授課時間

第

星期

年

日

月

節

第九章內部排序

第一節概述

排序的定義、穩定性、、分類和排序表的存儲結構表示。

第二節插入排序

直接插入排序的思想、算法和分析；希爾排序的思想、算法和分析。

授第三節交換排序

課冒泡排序的思想、算法和分析；快速排序的思想、算法和分析。內

第國節選擇排序

容簡單選擇排序的思想、算法和分析；樹形選擇排序的思想；堆的定義、篩選法

概建堆的過程、堆排序的算法和分析。

要第五節歸并排序

歸并排序的思想、算法和分析。

第六節基數排序

多關鍵字排序和鏈式基數排序。

第七節各種內部排序方法的比較討論

各種內部排序方法的比較，內部排序的時間復雜度的下界。

盲目的：掌握內部排序的基本方法

的基本要求：理解二路歸并排序、堆排序、基數排序的思想和算法，理解各種排序方

要法的特點；掌握排序的基本概念，掌握直接插入排序、希爾排序、簡單選擇排序、

求冒泡排序、快速排序的思想和算法。

重希爾排序、冒泡排序、堆排序、快速排序、二路歸并排序和基數排序。

點

雁■唯排序、快速排序、二路歸并排序和基數排序。

點

作

業

領

習

布10

置

參1.數據結構題集（C語言版），嚴蔚敏，清華大學出版社，2002。

考3.數據結構、算法與應用一C++語言描述，（美）SartajSahni著，汪詩林等譯，機書

械二業出版社,2002.

課型理論課學復習分鐘

時

主要教具投影、黑板分講授分鐘

配

教學方法講解、提問、不例指導分鐘

教學手段板書、課件總結分鐘

共8學時，其中2學時為習題課

備注

注：課型一欄填寫理論課、實驗課、習題課等

授課內容備注

第10章排序

10.1概述

為了便于查找，通常希翼計算機中的數據表是按關鍵碼有序的。

如有序表的折半查找，查找效率較高。還有，二叉排序樹、B-樹和B+樹

的構造過程就是一個排序過程。

排序(sorting)計算機程序設計中的一種重要操作，其功能是對一個數據元

素集合或者序列重新羅列成一個按關鍵碼有序的序列。

1.排序的定義

(1)排序的定義：

設｛Ri，0,卜是由n個記錄組成的文件，｛K「F，,卜｝是排序碼集合，

所謂排印是“將記錄按排序碼遞增(或者遞減)的羅翁

排序碼可以是主關鍵碼，也可以是次關鍵碼。

(2)穩定性

假設K「K」(105麗)，且在排序前的序列中5率先于％(即i<j),若在排序后

的序列‘中Rj仍率先于R「則稱所用的排序務法是穩,定的，否則是不穩

定的。

(3)排序的分類：

待排序的記錄在排序過程中全部存放在內存的稱為內排序，如果排序過

程中需要使用外存的稱為外排序。

按排序原則，排序分為：

①插入排序；

②選擇排序；

③交換排序

④分配排序

⑤歸并排序

⑥外部排序

按排序所需的工作量，排序分為：

①簡單排序方法，其時間復雜度為O(n2)；

②先進的排序方法，其時間復雜度為O(nlogn)；

③基數排序，其時間復雜度為O(dn.)；

(4)排序中的基本操作：

①比較關鍵碼大小

②挪移記錄

(5)對于待排序的記錄序列，有三種常見的存儲表示方法。

①向量結構，即將待排序的記錄存放在一組地址連續的存儲單元中。

②鏈表結構。

③記錄向量與地址向量結合，即將待排序記錄存放在一組地址連續的

存儲單元中，同時另設一個指示各個記錄位置的地址向量。

為簡單起見，數據的存儲結構采取向量的存儲結構：

#definen20〃記錄數

typedefintkeytype;

typedefstruct{

keytypekey;

datatypeother;

}rectype;rectyrp[en+l];

(6)排序算法的評價：

①算法的執行時間

②算法執行時所需的附加空間

10.2插入排序

基本原理：

每步將一個待排序的對象，按其關鍵字大小，插入到前面己經排好序的

一組對象適當位置上，直到對象全部插入為止。

10.2.1直接插入排序

1直接插入排序的基本思想

先假定第1個記錄為有序序列，然后從第2條記錄開始，挨次將記錄插

入到前面已經有序的序列中，直至全部記錄有序。

普通情況下，第i趟宜接插入排序：將r⑴插入到己經有序的序列

中，使其變成有序序列叩.用。

整個排序進行n-l趟插入。

2示例:

初始：|49]38659776132749

3算法:

voidInsertSort(rectypeR[],intn){

intij;

for(i=2;i<n;i++){

R[0]=R[i];

for(j=i-1;R[0].key<R|j].key;j-)

R[j+i]=RUI；

RU+1]=R[0]

)

)

4算法分析：

空間效率；只需要一個記錄的輔助空間。

時間效率：

比較記錄的次數為：

最?。荷?次；最大:(n+2)(n-l)/2次

挪移記錄的次數：

最?。?(n-l)最大:(n+4)(n-l)/2

平均情況：0(m)

10.2.2折半插入排序

1、折半插入排序：

將直接插入排序的查找過程改用折半查找。由此實現的排序稱為二分法

插入排序。

10.2.3希爾排序(Shell'sSort)

1、希爾排序：

shell排序又稱縮小增量排序(DiminishingIncrementSort)?

先將整個待排記錄序列分割成若干個子序列分別進行直接插入排序，待

整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排

序，就可以完成整個的排序工作。

利用下面兩點:

當n很小時，直接插入排序的效率較高；

當待排記錄序列基本有序時，直接插入排序的效率也較高。shell排序對直

接插入排序算法進行改進。

例：原始序列4938659713762749’

voidshellSort(rectyper[],intn,intd[],intk){

for(l=0;l<k;l++){

dk=d[l];

for(i=dk+l;i<=n;i++){

r[0]=r[i];

for(j=i-dk;(j>0&&R[j].key>r[0].key);j-=dk)

r[j+dk]=r[j];

Rlj+dk尸r[0];

)

)

)

2、算法分析：

Shell排序的平均比較次數和平均挪移次數都為0(nl.3)擺布

Shell排序算法中增加了一個輔助空間。

Shell排序是不穩定的。

10.3交換排序

交換排序基本思想：

兩兩比較待排序記錄的排序碼，交換不滿足排序要求的偶對，直到全部

有序。

10.3.1冒泡排序(BubbleSort)

1、基本思想：

設待排序記錄順序存放在g,《中：

挨次比較(R,R,),(R,R)JR3),不滿足順序則交換，結果，最大者

在R中。這叫一次起泡。

此后，再對“存放在R,R,R,,R中n-1個記錄作同樣處理,結果，最大

123n-1

者在R中。

O

n-1次起泡能完成排序。設置標志noswap表示本次起泡是否有交換，若

無交換，表示排序完成。

2、示例：

3、算法：

voidbubbleSort(rectypeR[],intn){

i=l;flag=l;

for(i=l;i<n&&flag;i++){

flag=0;

for(j=l;j<=n-i;j++)

if(R[j].key>R[j+l].key)(

temp=R[j+l]；

RLi+i]=R|j];

R[j]=temp;

flag=1；

)

)

)

4、算法分析：

起泡排序的最壞時間復雜度為0(n2),平均時間復雜度為0(n2)?

起泡排序算法中增加一個輔助空間temp,輔助空間為S(n)=O(l)。

起泡排序是穩定的。

10.3.2快速排序(QuickSort)

1、基本思想：

快速排序的基本思想是：從待排序記錄序列中選取一個記錄(通常選取

第一個記錄)作為“樞軸”，通過一趟排序(一次劃分)將待排記錄分割

成獨立的兩部份，其中一部份記錄的關鍵字比樞軸小，另一部份記錄

的關鍵字比樞軸大。然后則可分別對這兩部份記錄繼續進行劃分，以達

到整個序列有序。

1基本思想：

一趟快速排序(一次劃分)的具體做法是：

附設兩個指針low和high,它們的初值分別是一個序列的第一個和最后一

個記錄的位置,設樞軸記錄的關鍵字為pivotKey,在首先從high所指位置

起向前搜索直到第一個關鍵字小于pivotKey的記錄和樞軸記錄交換，然

后從low所指位置起向后搜索，找到第一個關鍵字大于pivotKey的記錄和

樞軸記錄互相交換，重復交替這兩步直到k)w=high為止。

2、示例：

設記錄的關鍵碼序列為：

4938659776132749

對其進行快速排序。

3、算法：

intPartition(rectypeR[],intn,intlow,inthigh)

(

pivotkey=R[low].key;

while(low<high){

while((low<high)&&(R[high].key>=pivotkey))

-high;

r[low]=r[high];

while((low<high)&&(R[low].key<=pivotkey))

++10W；

r[high]=r[Iow];

)

r[low]=pivotkey;

returnlow;

}

voidQSort(rectypeR[],intn,intlow,inthigh){

if(low<high){

pivotloc=Partition(R,n,low,high);

QSort(R,low,pivotloc-1);

QSort(R,pivotloc+l,high);

)

}

voidQuickSort(rectypeR||,intn){

QSort(R,n,l,n);

)

4、算法分析：

謖壞情況下，即當初始序列已經有序時，快速排序退化為起泡排序，為

0(112)。

最好時間復雜度為O(nlogn)o

平均時間復雜度是T(n)=O(nlogn)o

算法需要一個?？臻g實現遞歸「棧的大小取決于遞歸調用的深度，最多

不超過n,理想情況下不超過logn：所以快速排序的輔助空間最壞為

S(n)=O(n),最好為S(n)=O(logn)o

快速排序是不穩定的。

10.4選擇排序

選擇排序(SelectionSort)的基本思想是：每一趟在n-i+l(i=L2,n-1)

個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。

10.4.1簡單選擇排序(SimpleSelectionSort)

1、基本思想：

第i趟簡單選擇排序是指通過n-i次關鍵字的比較，從n-i+1個記錄中選出

關鍵字最小的記錄，并和第i個記錄進行交換。共需進行i-1趟比較，直

到所有記錄排序完成為止。

2、示例：

3、算法：

voidSelectSort(rectypeR[],intn){

for(i=l;i<=n-l;i++){

k=i;

for(j=i+1;j<=n;j++)

if(R[j].key<R[k].key)k=j;

if(k!=i){

temp=R[i];

R[i]=R[k];

R|k]=temp;

)

)

4、算法分析：

直接選擇排序的比較次數與文件初始狀態無關。

直接選擇排序的時間復雜度：

挪移：最好：0最壞：3(n-1)

比較：n(n-l)Z2

總的時間復雜度：0(n2)

穩定性：不穩定

10.4.2樹形選擇排序(TreeSelectionSort)

1基本思想：

簡單選擇排序的主要操作是比較，要提高它的速度必須減少比較的次數。

而實際上如果能利用以前的比較結果則可以提高排序速度。

樹形選擇排序(TreeSelectionSort),又稱錦標賽排序(Tournamentsort),

其方法是：首先對n個記錄的關鍵字進行兩兩比較，然后在n/2個較小

者之間再進行兩兩比較，如此重復直到選出最小關鍵字的記錄為止。

然后對剩下的記錄作同樣的操作，選出具有次小關鍵字的記錄。這個

過程可以用一個徹底二叉樹來表示。

2示例：

3算法分析：

在樹型選擇排序中，含有n個葉子節點的徹底二叉樹的深度為「log2nl+1，

則在樹型選擇排序中，每選擇一個小關鍵字需要進行「log2n1次比較，

因此其時間復雜度為O(nlog2n)。挪移記錄次數不超過比較次數，故總的

算法時間復雜度為O(nlog2n)。

缺點是使用了較多的輔助空間(n-1),并且和“最大值”進行了多余的比較。

10.4.3堆排序(HeapSort)

1堆的定義：

堆排序是對樹型選擇排序的進一步改進。采用堆排序時，只需要一個記

錄大小的輔助空間。

1964年Willioms提出了堆排序。

堆的定義：n個元素的序列｛k,k,,k｝當且僅當滿足如下關系時，稱之

I2n

為堆。

kkkk

i2ii2i

kkkk

i2H-1i2i+l

(i=l,2,,n/2)

若將和此序列對應的一維數組看成是一個徹底二叉樹，則堆的含義表明，

徹底二叉樹中所有非終端結點的值均不小于(或者不大于)其擺布孩子結

點的值。

2堆排序的基本思想：

若序列｛k(k,,k)是堆，則堆頂元素必為序列中n個元素的最大值

(或者最小

如果在輸出堆頂的最大值后，使得剩余n-1個元素的序列重又建成一個

堆，則得到次大值。

反復執行便能得到所有記錄的有序序列，這個過程稱為堆排序。

現在剩下兩個問題：

(1)如何由一個無序序列建成一個堆；

(2)如何在輸出堆頂元素后，調整剩余元素為一個新的堆。

問題1:當堆頂元素改變時，如何重建堆？

“篩選”法調整成堆。

問題2:如何由一個任意序列建初堆？

一個任意序列看成是對應的徹底二叉樹，由于葉結點可以視為單元素

的堆，于是可以反復利用“篩選”法，自底向上逐層把所有子樹調整為

堆，直到將整個徹底二叉樹調整為堆。

對無序序列｛49,38,65,97,76,13,27,49｝建堆示例：

問題3:如何利用堆進行排序？

進行堆排序的步驟：①將待排序記錄按照堆的定義建初堆，并輸出堆

頂元素：②調整剩余的記錄序列，利用篩選法將前n-i個元素重新篩選

為一個新堆，再輸出堆頂元素；③重復執行步驟②n-1次進行篩

選，新篩選成的堆會越來越小，而新堆后面的有序關鍵字會越來越多,

最后使待排序記錄序列成為一個有序的序列，這個過程稱之為堆排序。

例：初始序列為

26,5,77,1,61,11,59,15,48,19

3算法：

voidSift(rectypeR[],ints;intm){〃篩選算法

temp=R[s];

for(j=2*s;j<=m;j*=2){

if((j<m)&&(R[j].key<R[j+l|.key))

j++；

if(temp.key>=R|j].key)break;

R[s]=R[j]；s=j;

)

R|s]=temp;

)

〃堆排序算法

voidHeapSort(rectypeR[],intn){

for(i=n/2;i>=l;i??)〃初始建堆

Sift(R,i,n);

for(i=n;i>l;i-){

temp=R[l];R[l]=R[i];

R[i]=temp;

Sift(R,l,i-l);

)

)

4算法分析：

初始建堆比較次數為：O(n)

排序中比較次數為：<0(n*Iog2n)0

挪移次數小于比較次數。

在最壞的情況下，時間復雜度也是O(nlogn)。

且僅需一個記錄大小的輔助空間。

堆排序合用于n值較大的情況。

堆排序是不穩定的排序方法。

10.5歸并排序

1基本思想：

歸并的含義是將兩個或者兩個以上的有序表合并成一個有序表。利用歸

并的思想就可以實現排序。假設初始的序列含有n個記錄，可以看成n

個有序的子序列，每一個子序列的長度為1,然后兩兩歸并，得到n/2

個長度為2或者1的有序子序列；再兩兩歸并，如此重復直到得到一個長度

為n的有序序列為止。這種排序方法稱為二路歸并排序。

2示例：

voidMerge(rectypeR[],rectypeR1[],intlow,intmid,inthigh){

i=low;j=mid+l;k=low;

while((i<=mid)&&(j<=high))

if(R[i].key<=R[j].key)Rl[k++]=R[i++];

elseRl[k++]=R[j++];

while(j<=mid)Rl[k++]=R[i4-+];

while(j<=high)RI[k++]=R[j4-+];

\

]

voidMSort(rectypeR|],rectypeRl[],ints,intt){

if(s==t)rl[s]=r[s];

else{

m=(s+t)/2;

MSort(R,R2,s,m);

MSort(R,R2,m+l,t);

Merge(r2,rl,s,m,t);

)

voidMergeSort(rectypeR[],intn){

MSort(rj,l,n);

)

時間復雜度:O(nlogn)

空間復雜度:和待排出錄等量的空間.

二路歸并算法是穩定的.

普通情況下很少用于內部排序.

10.6分配排序

分配類排序則利用分配和采集兩種基本操作，基數類排序就是典型的分

配類排序。

分配排序的思想是把排序碼分解成若干部份，然后通過對各個部份排序

碼的分別排序，最終達到整個排序碼的排序。

10.6.1概述

普通情況下，假設文件F有n個記錄

F=(R,R,?R)

01n-l

且每一個記錄R.的排序碼中含有d個部份(k。，kk),則文件F

11011id-1

對排序碼(k,k,,,,k)有序是指：文件中任意兩個記錄R和R(0WiW

jW

01d-1ij

不謫足詞典次序有序關系

(k/k,i；<(k.o，k,晨)

其中k稱為最高位排序碼，k,稱為最低位排序碼。實現分配排序，有兩

種方點：第一種是先對最高檢'排序碼k排序，稱為最高位優先法(Most

0

SignificantDigitfirst)。第二種是先對最低位排序碼k排序，稱為

d-l

最低位優先法(LeastSignificantDigitfirst)。

例如：

我們可以將一副撲克牌的排序過程看成由花色和面值兩個關鍵字進行排

序的問題。若規定花色和面值的順序如下：

花色：梅花(方塊<紅桃<黑桃

面值:A<2<3<?<10<J<Q<K

并進一步規定花色的優先級高于面值，則一副撲克牌從小到大的順序為：

梅花A,梅花2,,,,梅花K；方塊A,方塊2,,,,方塊K；紅桃A,紅

桃2,紅桃K；黑桃A,黑桃2,,,,黑桃K。

最高位優先：先按花色分成有序的四類，然后再按面值對每一類從小到

大排序。

最低位優先：先按面值從小到大把牌擺成13疊(每疊4張牌)，然后將

每疊牌按面值的次序采集到一起，再對這些牌按花色擺成4疊，每疊有

13張牌，最后把這4疊牌按花色的次序采集到一起，于是就得到了有序

序列。

低位優先法比高位優先法簡單，高位優先排序必須將文件逐層分割成若

干子文件，然后各子文件獨立排序；低位優先排序不必分成子堆，對每

個排序碼都是整個文件參加排序，且可通過若干次“分配”和“采集”

實現排序。但對K(0<=i<=d-2)進行排序時，只能用穩定的排序方法。

下面將介紹的基數排序就是用排序碼低位優先法的思想對排序碼進行分解

后排序的一種方法。

10.6.2鏈式基數排序

采用基數排序首先把每一個排序碼看成是一個d元組：

K=(K,K.?,K)

110i1id-1

其中每一個K都是集合{C,C,C}(C<C<?<C)中的值，即CWK

i01r-101r-l0ij

WC(0WiWnT,0WjWdT),其中r稱為基數。排序時先按K從小

r-|