《數(shù)據(jù)結(jié)構(gòu)與算法》

數(shù)據(jù)結(jié)構(gòu)與算法

DataStructureAlgorithms

煙臺南山學(xué)院信息科技學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)組.數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容.9.1概述9.2插入排序9.3交換排序9.4選擇排序9.5歸并排序9.6基數(shù)排序第9章內(nèi)部排序.9.1概述1.什么是排序？將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序3.排序算法的好壞如何衡量？時間效率——排序速度（即排序所花費的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性A和B的關(guān)鍵字——若兩個記錄值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的?！阌诓檎遥?4.什么叫內(nèi)部排序？什么叫外部排序？

——若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；——若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。注：外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時放入外存，顯然外部排序要復(fù)雜得多。5.待排序記錄在內(nèi)存中怎樣存儲和處理？①順序排序——排序時直接移動記錄；②鏈表排序——排序時只移動指針；③地址排序——排序時先移動地址，最后再移動記錄。注：地址排序中可以增設(shè)一維數(shù)組來專門存放記錄的地址。.注：大多數(shù)排序算法都是針對順序表結(jié)構(gòu)的(便于直接移動元素)6.順序存儲（順序表）的抽象數(shù)據(jù)類型如何表示？Typedefstruct{//定義每個記錄（數(shù)據(jù)元素）的結(jié)構(gòu)KeyTypekey;//關(guān)鍵字

InfoTypeotherinfo;//其它數(shù)據(jù)項}RecordType;Typedefstruct{//定義順序表的結(jié)構(gòu)RecordTyper[MAXSIZE+1];//存儲順序表的向量

//r[0]一般作哨兵或緩沖區(qū)intlength;//順序表的長度}SqList;#defineMAXSIZE20//設(shè)記錄不超過20個typedefintKeyType;//設(shè)關(guān)鍵字為整型量（int型）.7.內(nèi)部排序的算法有哪些？——按排序的規(guī)則不同，可分為5類：插入排序交換排序（重點是快速排序）選擇排序歸并排序基數(shù)排序d＝關(guān)鍵字的位數(shù)(長度)——按排序算法的時間復(fù)雜度不同，可分為3類：簡單的排序算法：時間效率低，O(n2)先進的排序算法:時間效率高，O(nlog2n)基數(shù)排序算算法：時間效率高，O(d×n).9.2插入排序插入排序的基本思想是：插入排序有多種具體實現(xiàn)算法：1)直接插入排序2)折半插入排序3)表插入排序4)希爾排序每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。.1)直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請寫出直接插入排序的中間過程序列。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】

在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。最簡單的排序法！.直接插入排序算法

VoidInsertSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//設(shè)定監(jiān)視哨

j=i-1;if(LT(L.r[i].key,L.r[i-1].key))for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];//記錄后移L.r[j+1]=L.r[0];//插入記錄}.例2：關(guān)鍵字序列T=（21，25，49，25*，16，08），

請寫出直接插入排序的具體實現(xiàn)過程。*表示后一個25i=121254925*16080123456暫存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假設(shè)該序列已存入一維數(shù)組V[7]中，將V[0]作為緩沖或暫存單元（Temp）。則程序執(zhí)行過程為：21254925*21初態(tài)：164925*25211608完成!時間效率：O(n2)——因為在最壞情況下，所有元素的比較次數(shù)總和為（0＋1＋…＋n-1)→O(n2)。其他情況下還要加上移動元素的次數(shù)。空間效率：O（1）——因為僅占用1個緩沖單元算法的穩(wěn)定性：穩(wěn)定——因為25*排序后仍然在25的后面。.若設(shè)待排序的對象個數(shù)為n，則算法需要進行n-1次插入。最好情況下，排序前對象已經(jīng)按關(guān)鍵碼大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€對象的關(guān)鍵碼比較1次，移動2次對象。因此，總的關(guān)鍵碼比較次數(shù)為n-1，對象移動次數(shù)為2(n-1)。直接插入排序的算法分析.最壞情況下，第i趟插入時，第i個對象必須與前面i-1個對象都做關(guān)鍵碼比較，并且每做1次比較就要做1次數(shù)據(jù)移動。則總的關(guān)鍵碼比較次數(shù)KCN和對象移動次數(shù)RMN分別為.若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵碼比較次數(shù)和對象移動次數(shù)約為n2/4。因此，直接插入排序的時間復(fù)雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。.2）折半插入排序優(yōu)點：比較的次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。時間效率：雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少，所以排序效率仍為O(n2)?？臻g效率：

O（1）穩(wěn)定性：穩(wěn)定對應(yīng)程序見教材P267（僅用于順序表）新元素插入到哪里？討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？答：直接插入不僅可行，而且還無需移動元素，時間效率更高！折半插入排序的改進——2-路插入排序267在已形成的有序表中折半查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。但鏈表無法“折半”！.折半插入排序的算法分析折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。在插入第i

個對象時，需要經(jīng)過log2i+1

次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。因此，將n

個對象用折半插入排序所進行的關(guān)鍵碼比較次數(shù)為：n*log2n折半插入排序是一個穩(wěn)定的排序方法。.3）表插入排序基本思想：在順序存儲結(jié)構(gòu)中，給每個記錄增開一個指針分量，在排序過程中將指針內(nèi)容逐個修改為已經(jīng)整理（排序）過的后繼記錄地址。優(yōu)點：在排序過程中不移動元素，只修改指針?；貞洠孩阪湵砼判颉判驎r只移動指針；③地址排序——排序時先移動地址，最后再移動記錄。此方法具有鏈表排序和地址排序的特點。.1例：關(guān)鍵字序列T=(21，25，49，25*，16，08），

請寫出表插入排序的具體實現(xiàn)過程。解：假設(shè)該序列（結(jié)構(gòu)類型)已存入一維數(shù)組V[7]中，將V[0]作為表頭結(jié)點。則算法執(zhí)行過程為：i關(guān)鍵字V[i].key指針V[i].link0MaxNum121225349425*516608指向第1個元素指向頭結(jié)點初態(tài)i=1i=2i=3i=4i=5i=603456503102*表示后一個25.intLinkInsertSort(staticlinklis<Type>&list){

list.v[0].Key=MaxNum;

list.v[0].Link=1;

list.v[1].Link=0; //形成循環(huán)鏈表表插入排序的算法for(inti=2;i<=list.length;i++)

{

int

current=list.v[0].Link;//current=當(dāng)前記錄指針intpre=0; //pre=當(dāng)前記錄current的前驅(qū)指針while(list.v[current].Key<=list.v[i].Key){

pre=current;//current指針準(zhǔn)備后移,pre跟上；

current=list.v[current].Link;}

//找插入位置(即p=p->link)list.v[i].Link=current;//新記錄v[i]找到合適序位開始插入

list.v[pre].Link=i;//在pre與current之間鏈入

}}.表插入排序算法分析：①無需移動記錄，只需修改2n次指針值。但由于比較次數(shù)沒有減少，故時間效率仍為O(n2)。②空間效率肯定低，因為增開了指針分量（但在運算過程中沒有用到更多的輔助單元）。③穩(wěn)定性：25和25*排序前后次序未變，穩(wěn)定。討論：此算法得到的只是一個有序鏈表，查找記錄時只能滿足順序查找方式。改進：可以根據(jù)表中指針線索，很快對所有記錄重排，形成真正的有序表（順序存儲方式），從而能滿足折半查找方式。具體實現(xiàn)見教材P269。.4）希爾（shell）排序（又稱縮小增量排序）基本思想：先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。技巧：子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。優(yōu)點：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。.38例：關(guān)鍵字序列T=(49，38，65，97,76,13,27,49*，55,04），請寫出希爾排序的具體實現(xiàn)過程。0123456789104938659776132749*5504初態(tài)：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*975576042738

65

49*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697算法分析：開始時dk

的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，dk

值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。r[i].voidShellSort(SqList&L，intdlta[]，intt){

//按增量序列dlta[0…t-1]對順序表L作Shell排序for(k=0；k<t；++k)ShellSort(L，dlta[k])；//增量為dlta[k]的一趟插入排序}//ShellSort時間效率：空間效率：O（1）——因為僅占用1個緩沖單元算法的穩(wěn)定性：不穩(wěn)定——因為49*排序后卻到了49的前面希爾排序算法（主程序）參見教材P272O(n1.25）～O（1.6n1.25）——經(jīng)驗公式dk值依次裝在dlta[t]中.附：希爾排序算法分析對特定的待排序?qū)ο笮蛄校梢詼?zhǔn)確地估算關(guān)鍵碼的比較次數(shù)和對象移動次數(shù)。但想要弄清關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒有人能夠做到。Knuth利用大量的實驗統(tǒng)計資料得出，當(dāng)n很大時，關(guān)鍵碼平均比較次數(shù)和對象平均移動次數(shù)大約在n1.25

到1.6n1.25

的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。.voidShellInsert(SqList&L，int

dk){

for(i=dk+1；i<=L.length；++i)if(r[i].key<r[i-dk].key){

r[0]=r[i]；

for(j=i-dk;j>0&&(r[0].key<r[j].key);j=j-dk) r[j+dk]=r[j]；r[j+dk]=r[0]；}}希爾排序算法（其中某一趟的排序操作）參見教材P272//對順序表L進行一趟增量為dk的Shell排序，dk為步長因子//開始將r[i]插入有序增量子表//暫存在r[0]//關(guān)鍵字較大的記錄在子表中后移//在本趟結(jié)束時將r[i]插入到正確位置.課堂練習(xí)：1.欲將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按字母升序重排，則初始步長為4的希爾排序一趟的結(jié)果是？答：原始序列：Q,H,C,Y,P,A,M,S,R,D,F,X

shell一趟后：2.以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫出執(zhí)行以下算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實現(xiàn)？①直接插入排序②希爾排序（取dk=5,3,1）P,Q,R,A,D,H,C,F,M,S,X,Y答：顯然，直接插入排序方法易于在鏈表上實現(xiàn)；但希爾排序方法因為是按增量選擇記錄，不易于在鏈表上實現(xiàn)。

兩種排序方法的中間狀態(tài)分別描述如后：.原始序列：

256，301，751，129，937，863，742，694，076，438[256，301]，751，129，937，863，742，694，076，438[256，301，751]，129，937，863，742，694，076，438[129，256，301，751]，937，863，742，694，076，438[129，256，301，751，937]，863，742，694，076，438[129，256，301，751，863，937]，742，694，076，438[129，256，301，742，751，863，937]，694，076，438[129，256，301，694，742，751，863，937]，076，438[076，129，256，301，694，742，751，863，937]，438[076，129，256，301，438，694，742，751，863，937]直接插入排序第1趟第2趟第3趟第4趟第5趟第6趟第7趟第8趟第9趟.原始序列：

256，301，751，129，937，863，742，694，076，438希爾排序(取dk=5,3,1)256，301，751，129，937，863，742，694，076，438256，301，751，129，937，863，742，694，076，438256，301，694，129，937，863，742，751，076，438256，301，694，076，937，863，742，751，129，438256，301，694，076，438，863，742，751，129，937第1趟dk=5第2趟dk=3第3趟dk=1256，301，694，076，438，863，742，751，129，937256，301，694，076，438，863，742，751，129，937076，301，694，256，438，863，742，751，129，937076，301，694，256，438，863，742，751，129，937076，301，694，256，438，863，742，751，129，937076，301，129，256，438，694，742，751，863，937076，301，129，256，438，694，742，751，863，937076，301，129，256，438，694，742，751，863，937076，129，256，301，438，694，742，751，863，937.9.3交換排序兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。交換排序的主要算法有：1)冒泡排序2)快速排序交換排序的基本思想是：.1)冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲結(jié)構(gòu)例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出冒泡排序的具體實現(xiàn)過程。21，25，49，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，16，08，25，

25*，4916，08，21，

25，

25*，4908，16，

21，

25，

25*，49初態(tài)：第1趟第2趟第3趟第4趟第5趟.冒泡排序的算法分析時間效率：O（n2)—因為要考慮最壞情況空間效率：O（1）—只在交換時用到一個緩沖單元穩(wěn)定性：

穩(wěn)定—25和25*在排序前后的次序未改變詳細分析：最好情況：初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做n-1次關(guān)鍵碼比較，不移動對象。最壞情形：初始排列逆序，算法要執(zhí)行n-1趟起泡，第i趟(1

i

n)

做了n-i

次關(guān)鍵碼比較，執(zhí)行了n-i

次對象交換。此時的比較總次數(shù)KCN和記錄移動次數(shù)RMN為：.2）快速排序從待排序列中任取一個元素(例如取第一個)作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個。此時便為有序序列了?；舅枷耄簝?yōu)點：因為每趟可以確定不止一個元素的位置，而且呈指數(shù)增加，所以特別快！前提：順序存儲結(jié)構(gòu)

.()，設(shè)以首元素為樞軸中心例1：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出快速排序的算法步驟。21，25，49，25*，16，08初態(tài)：第1趟：第2趟：第3趟：討論：1.這種不斷劃分子表的過程，計算機如何自動實現(xiàn)？2.“快速排序”是否真的比任何排序算法都快？08，16，21，25，

25*，(49)2116，08，()25，25*，49(08)，16，21，25，(25*，49).1.這種不斷劃分子表的過程，計算機如何自動實現(xiàn)？編程時：①每一趟的子表的形成是采用從兩頭向中間交替式逼近法；②由于每趟中對各子表的操作都相似，主程序可采用遞歸算法。見教材P275intPartition(SqList&L,intlow,inthigh){//一趟快排//交換子表r[low…h(huán)igh]的記錄，使支點（樞軸）記錄到位，并返回其位置。返回時，在支點之前的記錄均不大于它，支點之后的記錄均不小于它。

r[0]=r[low];//以子表的首記錄作為支點記錄，放入r[0]單元（續(xù)下頁）一趟快速排序算法（針對一個子表的操作）.pivotkey=r[low].key;//取支點的關(guān)鍵碼存入pivotkey變量while(low<high){

//從表的兩端交替地向中間掃描 while(low<high&&r[high].key>=pivotkey)--high; r[low]=r[high];//將比支點小的記錄交換到低端； while(low<high&&r[low].key<=pivotkey)++low; r[high]=r[low];//將比支點大的記錄交換到高端；

}r[low]=r[0];//支點記錄到位； returnlow;//返回支點記錄所在位置。}//Partition.Low=high=3，本趟停止，將支點定位并返回位置信息例2：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出快速排序算法的一趟實現(xiàn)過程。r[i]0123456初態(tài)21254925*1608第1趟highlow210825164925*321pivotkey=2108251649(08

，16）21（25*，49，25）25*跑到了前面，不穩(wěn)定！.j從高端掃描尋找小于pivot的元素i從低端掃描尋找大于pivot的元素i=low;j=high;r[0]=r[low];pivot=r[low].key;i<ji<j&&r[j].key>=pivot--j;r[i]=r[j];i<j&&r[i].key<=pivot--i;r[j]=r[i];r[i]=r[0];returnok;YYYNNN一趟快速排序算法流程圖.voidQSort(SqList&L,intlow,inthigh

){

if(low<high){

pivot=Partition(L,low,high);

QSort(L,low,pivot-1);

QSort(L,pivot+1,high);}}整個快速排序的遞歸算法：見教材P276//長度>1//對順序表L中的子序列r[low…h(huán)igh]

作快速排序//一趟快排，將r[]一分為二//在左子區(qū)間進行遞歸快排，直到長度為1//在右子區(qū)間進行遞歸快排，直到長度為1//QSort新的lowvoidQuickSort(SqList&L){QSort(L,

1,L.length

);}對順序表L進行快速排序的操作函數(shù)為：.例3：以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行快速算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)。原始序列：

256，301，751，129，937，863，742，694，076，438快速排序第1趟第2趟第3趟第4趟256，301，751，129，937，86