第-章-內(nèi)部排序2優(yōu)秀文檔

第10章內(nèi)部排序嘉應(yīng)學(xué)院數(shù)學(xué)系數(shù)據(jù)結(jié)構(gòu)講義-插入排序數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容10.1概述1.什么是排序？將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

定義：設(shè)有記錄序列：{R1、R2…Rn}其相應(yīng)的關(guān)鍵字序列為：{K1、K2…Kn};若存在一種確定的關(guān)系：Kx<=Ky<=…<=Kz，將記錄序列{R1、R2…Rn}排成按該關(guān)鍵字有序的序列：{Rx、Ry…Rz}，這樣的操作稱之為排序。2.排序的目的是什么？3.排序算法的好壞如何衡量？時間效率——排序速度空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性——若兩個記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的?！阌诓檎遥?.什么叫內(nèi)部排序？什么叫外部排序？

——若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；——若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。——按排序的規(guī)則不同，可分為5類：插入排序（希爾排序）交換排序（快速排序）選擇排序（堆排序）歸并排序基數(shù)排序——按排序算法的時間復(fù)雜度不同，可分為3類：簡單的排序算法：時間效率低，O(n2)先進的排序算法:時間效率高，O(nlog2n)基數(shù)排序算算法：時間效率高，O(d×n)5.內(nèi)部排序的算法有哪些？大多數(shù)排序算法都有兩個基本的操作：（1）比較兩個關(guān)鍵字的大?。?）將記錄從一個位置移動到另一個位置記錄序列的存儲方式：（1）順序存儲

（2）靜態(tài)鏈表（3）地址在最好情況下，即待排記錄序列已經(jīng)是從小到大排好順序時，其時間復(fù)雜度為O(n)。將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。KeyTypekey;//關(guān)鍵字直接插入排序的算法分析例如（25，21，49，26，56，76）for(i=2;i<=l->length;i++)voidInsertsort(SqList*l)【3,6,13，31】,9,27,5,11{inti,j;將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。若存在一種確定的關(guān)系：最壞情況下，第i趟插入時，第i個對象必須與前面i-1個對象都做關(guān)鍵碼比較，并且每做1次比較就要做1次數(shù)據(jù)移動。j--;大多數(shù)排序算法都有兩個基本的操作：【3,5,6,9,13，27,31】,11這樣的操作稱之為排序。注：大多數(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型）10.2插入排序插入排序的基本思想是：插入排序有多種具體實現(xiàn)算法：1)直接插入排序2)折半插入排序3)希爾排序每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。1)直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請寫出直接插入排序的中間過程序列?！?3】,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)位置插入，把原來位置上的元素向后順移。例2：關(guān)鍵字序列T=（21，25，49，25*，16，08），

請寫出直接插入排序的具體實現(xiàn)過程。i=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完成!直接插入排序編程實現(xiàn)直接插入排序?qū)?yīng)程序參見教材P265。voidInsertsort(SqList*l){inti,j;for(i=2;i<=l->length;i++){l->r[0]=l->r[i];j=i-1;while(l->r[0].key<l->r[j].key){l->r[j+1]=l->r[j];j--;}l->r[j+1]=l->r[0];}}

若設(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)定

新元素插入到哪里？在已形成的有序表中折半查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？折半插入排序的改進——2-路插入排序見教材P267。但鏈表無法“折半”！答：直接插入不僅可行，而且還無需移動元素，時間效率更高！例2：關(guān)鍵字序列T=（21，25，49，25*，16，08），

請寫出直接插入排序的具體實現(xiàn)過程。i=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完成!直接插入排序直接插入排序的改進算法的平均時間復(fù)雜度為O(n2)。在最好情況下，即待排記錄序列已經(jīng)是從小到大排好順序時，其時間復(fù)雜度為O(n)。當(dāng)待排記錄基本有序時，算法的效率也比較高。例如（25，21，49，26，56，76）當(dāng)n值很小時，算法效率也比較高。

希爾排序（又稱縮小增量排序）其基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。具體做法為：10.2.3希爾排序?qū)⒂涗浶蛄蟹殖扇舾勺有蛄?，分別對每個子序列進行插入排序。其中，d

稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為1。例如：將n個記錄{R[1]…R[n]}分成d個子序列：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}希爾排序（又稱縮小增量排序）其基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。分析：開始時dk的值較大，子序列中的對象較少，排序速度較快；注：大多數(shù)排序算法都是針對順序表結(jié)構(gòu)的(便于直接移動元素)中的關(guān)鍵碼按從小到大的順序進行排序，則初始步長為4的希爾排序一趟的結(jié)果是？//r[0]一般作哨兵或緩沖區(qū)希爾排序（又稱縮小增量排序）其基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}while(l->r[0].例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），KeyTypekey;//關(guān)鍵字把r[i]暫存在第0號單元；請寫出直接插入排序的中間過程序列。{K1、K2…Kn};隨著排序進展，dk值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。插入排序有多種具體實現(xiàn)算法：【3,6,13，31】,9,27,5,11內(nèi)部排序的算法有哪些？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

6549*9755135576045513270427044949*4949*76387665

65

9797551327044949*3876

65

971327

0449*

76

97

分析：開始時dk

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

值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。r[i]練習(xí)欲將序列：(8,5,2,12,7,1,6,10,9,3,4,11)中的關(guān)鍵碼按從小到大的順序進行排序，則初始步長為4的希爾排序一趟的結(jié)果是？希爾排序的實現(xiàn)取定步長序列，如dk=5,3,1。對每一步長dk，重復(fù)執(zhí)行如下過程：把每一子序列第一個元素看成是有序的，對后面的每一個元素r[i]，重復(fù)執(zhí)行如下過程：把r[i]暫存在第0號單元；尋找相應(yīng)子序列中應(yīng)該插入的位置：從后向前依次比較相應(yīng)子序列中的元素，直到找到不大于r[i]的元素。把r[i]放到適當(dāng)?shù)奈恢?。InfoTypeotherinfo;//其它數(shù)據(jù)項{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}將記錄序列{R1、R2