數(shù)據(jù)結(jié)構(gòu)排序-課件

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1PPT課件數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1PPT課件10.1概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序第10章內(nèi)部排序2PPT課件10.1概述第10章內(nèi)部排序2PPT課件10.1概述1.什么是排序？將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序

——便于查找！

3PPT課件10.1概述1.什么是排序？2.排序的目的是什么？10.1概述3.排序算法的好壞如何衡量？時(shí)間效率——排序速度（即排序所花費(fèi)的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小若排序算法所需的輔助空間不依賴問題的規(guī)模n，即空間復(fù)雜度是O(1)，則稱排序方法是就地排序，否則是非就地排序。穩(wěn)定性——若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。

4PPT課件10.1概述3.排序算法的好壞如何衡量？4PPT課件4.什么叫內(nèi)部排序？什么叫外部排序？

——若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；內(nèi)部排序基本操作有兩種：◆比較兩個(gè)關(guān)鍵字的大小；(比不可少的操作)◆存儲(chǔ)位置的移動(dòng)?！舸判蛴涗浺徊糠衷趦?nèi)存，一部分在外存，則稱為外部排序。注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時(shí)放入外存，顯然外部排序要復(fù)雜得多。

5PPT課件4.什么叫內(nèi)部排序？什么叫外部排序？——若待排序記錄都5.待排序記錄在內(nèi)存中怎樣存儲(chǔ)和處理？處理方式：①順序排序——數(shù)據(jù)間的邏輯順序關(guān)系通過其物理存儲(chǔ)位置的相鄰來體現(xiàn)，排序時(shí)直接移動(dòng)記錄；

適合數(shù)據(jù)較少的情況?、阪湵砼判颉獢?shù)據(jù)間的邏輯順序關(guān)系通過結(jié)點(diǎn)中的指針體現(xiàn)，排序時(shí)只修改指針，不移動(dòng)數(shù)據(jù)；③地址排序——數(shù)據(jù)存儲(chǔ)在一段連續(xù)地址的空間，構(gòu)造一個(gè)輔助表保持各數(shù)據(jù)的存放地址（指針），排序時(shí)先修改輔助表中的地址，最后再移動(dòng)記錄。

②③適合數(shù)據(jù)較多的情況!6PPT課件5.待排序記錄在內(nèi)存中怎樣存儲(chǔ)和處理？處理方式：6PPT課件注：大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的(便于直接移動(dòng)元素)6.順序存儲(chǔ)（順序表）的抽象數(shù)據(jù)類型如何表示？Typedefstruct{//定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu)

KeyTypekey;//關(guān)鍵字

InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RecordType;Typedefstruct{//定義順序表的結(jié)構(gòu)

RecordTyper[MAXSIZE+1];//存儲(chǔ)順序表的向量

//r[0]一般作哨兵或緩沖區(qū)

intlength;//順序表的長度}SqList;#defineMAXSIZE20//設(shè)記錄不超過20個(gè)typedefintKeyType;//設(shè)關(guān)鍵字為整型量（int型）7PPT課件注：大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的(便于直接移動(dòng)元素)67.內(nèi)部排序的算法有哪些？——按排序的規(guī)則不同，可分為5類：插入排序交換排序（重點(diǎn)是快速排序）選擇排序歸并排序基數(shù)排序d＝關(guān)鍵字的位數(shù)(長度)——按排序算法的時(shí)間復(fù)雜度不同，可分為3類：簡(jiǎn)單的排序算法：時(shí)間效率低，O(n2)先進(jìn)的排序算法:時(shí)間效率高，O(nlog2n)基數(shù)排序算法：時(shí)間效率高，O(d×n)8PPT課件7.內(nèi)部排序的算法有哪些？——按排序的規(guī)則不同，可分為510.2插入排序插入排序的基本思想是：插入排序有多種具體實(shí)現(xiàn)算法：

1)直接插入排序

2)折半插入排序

3)2路插入排序

4)希爾排序

每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。9PPT課件10.2插入排序插入排序的基本思想是：插入排序有多種具體1)直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請(qǐng)寫出直接插入排序的中間過程序列。【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)位置插入，把原來位置上的元素向后順移。最簡(jiǎn)單的排序法！10PPT課件1)直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（例2：關(guān)鍵字序列T=（21，25，49，25*，16，08），

請(qǐng)寫出直接插入排序的具體實(shí)現(xiàn)過程。*表示后一個(gè)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完成!時(shí)間效率：O(n2)——因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（0＋1＋…＋n-1)→O(n2)。其他情況下還要加上移動(dòng)元素的次數(shù)?？臻g效率：O（1）——因?yàn)閮H占用1個(gè)緩沖單元算法的穩(wěn)定性：穩(wěn)定——因?yàn)?5*排序后仍然在25的后面。

對(duì)應(yīng)程序參見教材P265。11PPT課件例2：關(guān)鍵字序列T=（21，25，49，25*，16，08VoidInsertSort(SqList&L){//對(duì)順序表L做直接插入排序

for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key))

//“<“,需將L.r[i]插入有序子表

{L.r[0]=L.r[i];//復(fù)制為哨兵

L.r[i]=L.r[i-1];for(j=i-2;LT(L.r[0].key,L.r[i].key);--j)L.r[j+1]=L.r[j];//記錄后移

L.r[j+1]=L.r[0];//插入到正確位置

}}//InsertSort12PPT課件VoidInsertSort(SqList&L)12P

不需要增加輔助空間若設(shè)待排序的對(duì)象個(gè)數(shù)為n，則算法需要進(jìn)行n-1次插入。最好情況下，排序前對(duì)象已經(jīng)按關(guān)鍵碼大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象的關(guān)鍵碼比較1次，對(duì)象不需要移動(dòng)。因此，總的關(guān)鍵碼比較次數(shù)為n-1。直接插入排序的算法分析13PPT課件不需要增加輔助空間直接插入排序的算法分析13PPT課件最壞情況下，第i趟插入時(shí)，第i個(gè)對(duì)象必須與前面i-1個(gè)對(duì)象都做關(guān)鍵碼比較，并且每做1次比較就要做1次數(shù)據(jù)移動(dòng)。則總的關(guān)鍵碼比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN分別為14PPT課件最壞情況下，第i趟插入時(shí)，第i個(gè)對(duì)象必須與前面i-1個(gè)對(duì)象都

若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。15PPT課件若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最2）折半插入排序優(yōu)點(diǎn)：比較的次數(shù)大大減少。時(shí)間效率：雖然比較次數(shù)大大減少，可惜移動(dòng)次數(shù)并未減少，

所以排序效率仍為O(n2)?？臻g效率：

O（1）穩(wěn)定性：穩(wěn)定對(duì)應(yīng)程序見教材P267（僅用于順序表）新元素插入到哪里？

在已形成的有序表中折半查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。16PPT課件2）折半插入排序優(yōu)點(diǎn)：比較的次數(shù)大大減少。VoidBInsertSort(SqList&L)//折半插入排序{for(i=2；i<=L.length；++i){L.r[0]=L.r[i]；//將L.r[i]暫存到L.r[0]low=1；high=i-1；

while(low<=high)//比較，折半查找插入位置

{m=(low+high)/2；//折半

if(LT(L.r[0].key,L.r[m].key))high=m-1；//插入點(diǎn)在低半?yún)^(qū)

elselow=m+1；//插入點(diǎn)在高半?yún)^(qū)

}//whilefor(j=i-1；j>=high+1；--j)L.r[j+1]=L.r[j]；//記錄后移

L.r[high+1]=L.r[0]；//插入

}//for}//BInsertSort17PPT課件VoidBInsertSort(SqList&L)初始i=2i=2i=2i=218PPT課件初始i=2i=2i=2i=218PPT課件初始i=8i=8i=819PPT課件初始i=8i=8i=819PPT課件初始i=8i=8i=8i=820PPT課件初始i=8i=8i=8i=820PPT課件初始i=8i=8i=8i=821PPT課件初始i=8i=8i=8i=821PPT課件折半插入排序的算法分析折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。在插入第i

個(gè)對(duì)象時(shí)，需要經(jīng)過log2i+1

次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。折半插入排序是一個(gè)穩(wěn)定的排序方法。22PPT課件折半插入排序的算法分析折半查找比順序查找快，所以折半插入排序討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？答：直接插入不僅可行，而且還無需移動(dòng)元素，時(shí)間效率更高！但鏈表無法“折半”！折半插入排序的改進(jìn)——2-路插入排序見教材P267。

（1）基本思想：P267

（2）舉例：P268圖10.2

（3）算法分析：移動(dòng)記錄的次數(shù)約為n2/82-路插入排序只能減少移動(dòng)記錄的次數(shù)，而不能絕對(duì)避免移動(dòng)記錄。實(shí)現(xiàn)是借助循環(huán)向量。=>

若希望在排序過程中不移動(dòng)記錄，只有改變存儲(chǔ)結(jié)構(gòu)，進(jìn)行表插入排序。23PPT課件討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？4）希爾（shell）排序（又稱縮小增量排序）基本思想：先將整個(gè)待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。技巧：子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)增量dk的記錄組成一個(gè)子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。24PPT課件4）希爾（shell）排序（又稱縮小增量排序）基本思想：先將38例：關(guān)鍵字序列T=(49，38，65，97,76,13,27,49*，55,04），請(qǐng)寫出希爾排序的具體實(shí)現(xiàn)過程。初態(tài)：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*975576042738

65

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

的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，dk

值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。r[i]25PPT課件38例：關(guān)鍵字序列T=(49，38，65，97,76,voidShellSort(SqList&L，intdlta[]，intt){

//按增量序列dlta[0…t-1]對(duì)順序表L作Shell排序

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

到1.6n1.25

的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。27PPT課件附：希爾排序算法分析對(duì)特定的待排序?qū)ο笮蛄校梢詼?zhǔn)確地估算關(guān)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//對(duì)順序表L進(jìn)行一趟增量為dk的Shell排序，dk為步長因子//開始將r[i]插入有序增量子表//暫存在r[0]//關(guān)鍵字較大的記錄在子表中后移//在本趟結(jié)束時(shí)將r[i]插入到正確位置28PPT課件voidShellInsert(SqList&L，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é)束時(shí)，關(guān)鍵字序列的狀態(tài)，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實(shí)現(xiàn)？①直接插入排序②希爾排序（取dk=5,3,1）P,Q,R,A,D,H,C,F,M,S,X,Y答：顯然，直接插入排序方法易于在鏈表上實(shí)現(xiàn)；但希爾排序方法因?yàn)槭前丛隽窟x擇記錄，不易于在鏈表上實(shí)現(xiàn)。

兩種排序方法的中間狀態(tài)分別描述如后：29PPT課件課堂練習(xí)：1.欲將序列（Q,H,C,Y,P,A原始序列：

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趟30PPT課件原始序列：256，301，751，129，937，863，原始序列：

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，93731PPT課件原始序列：256，301，751，129，937，863，10.3交換排序

兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹?。交換排序的主要算法有：

1)冒泡排序

2)快速排序交換排序的基本思想是：32PPT課件10.3交換排序1)冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲(chǔ)結(jié)構(gòu)例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請(qǐng)寫出冒泡排序的具體實(shí)現(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趟33PPT課件1)冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前for(j=0;j<n;j++) for(i=0;i<n-1-j;i++) if(a[i]>a[i+1])//需要互換 {t=a[i];a[i]=a[i+1];a[i+1]=t;}34PPT課件for(j=0;j<n;j++)34PPT課件冒泡排序的算法分析時(shí)間效率：O（n2)—因?yàn)橐紤]最壞情況空間效率：O（1）—只在交換時(shí)用到一個(gè)緩沖單元穩(wěn)定性：

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

i

n)

做了n-i

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

次對(duì)象交換。此時(shí)的比較總次數(shù)KCN和記錄移動(dòng)次數(shù)RMN為：35PPT課件冒泡排序的算法分析時(shí)間效率：O（n2)—因?yàn)橐紤]最壞情況2）快速排序

從待排序列中任取一個(gè)元素(例如取第一個(gè))作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個(gè)子表；然后再對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。此時(shí)便為有序序列了?；舅枷耄簝?yōu)點(diǎn)：因?yàn)槊刻丝梢源_定不止一個(gè)元素的位置，而且呈指數(shù)增加，所以特別快！前提：順序存儲(chǔ)結(jié)構(gòu)36PPT課件2）快速排序從待排序列中任取一個(gè)元素(()，設(shè)以首元素為樞軸中心例1：關(guān)鍵字序列T=(21，25，49，25*，16，08），請(qǐng)寫出快速排序的算法步驟。21，25，49，25*，16，08初態(tài)：第1趟：第2趟：第3趟：討論：1.這種不斷劃分子表的過程，計(jì)算機(jī)如何自動(dòng)實(shí)現(xiàn)？2.“快速排序”是否真的比任何排序算法都快？08，16，21，25*

，

25，(49)2108

，16，()25*，49，25(08)，16，21，25*

，(25，49)37PPT課件()，設(shè)以首元素為樞軸中心例討論1.這種不斷劃分子表的過程，計(jì)算機(jī)如何自動(dòng)實(shí)現(xiàn)？編程時(shí)：①每一趟的子表的形成是采用從兩頭向中間交替式逼近法；②由于每趟中對(duì)各子表的操作都相似，主程序可采用遞歸算法。見教材P275intPartition(SqList&L,intlow,inthigh){//一趟快排//交換子表r[low…h(huán)igh]的記錄，使支點(diǎn)（樞軸）記錄到位，并返回其位置。返回時(shí)，在支點(diǎn)之前的記錄均不大于它，支點(diǎn)之后的記錄均不小于它。

r[0]=r[low];//以子表的首記錄作為支點(diǎn)記錄，放入r[0]單元（續(xù)下頁）一趟快速排序算法（針對(duì)一個(gè)子表的操作）38PPT課件討論1.這種不斷劃分子表的過程，計(jì)算機(jī)如何自動(dòng)實(shí)現(xiàn)？編程時(shí)：pivotkey=r[low].key;//取支點(diǎn)的關(guān)鍵碼存入pivotkey變量while(low<high){

//從表的兩端交替地向中間掃描

while(low<high&&r[high].key>=pivotkey)--high; r[low]=r[high];//將比支點(diǎn)小的記錄交換到低端；

while(low<high&&r[low].key<=pivotkey)++low; r[high]=r[low];//將比支點(diǎn)大的記錄交換到高端；

}r[low]=r[0];//支點(diǎn)記錄到位；

returnlow;//返回支點(diǎn)記錄所在位置。}//Partition39PPT課件pivotkey=r[low].key;//取支點(diǎn)的關(guān)鍵Low=high=3，本趟停止，將支點(diǎn)定位并返回位置信息例2：關(guān)鍵字序列T=(21，25，49，25*，16，08），請(qǐng)寫出快速排序算法的一趟實(shí)現(xiàn)過程。highlow210825164925*321pivotkey=2108251649(08

，16）21

（25*，49，25）25*跑到了前面，不穩(wěn)定！40PPT課件Low=high=3，本趟停止，將支點(diǎn)定位并返回位置信息例2j從高端掃描尋找小于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一趟快速排序算法流程圖41PPT課件j從高端掃描i從低端掃描i=low;j=high;r[0]voidQSort(SqList&L,intlow,inthigh

){

if(low<high){

pivot=Partition(L,low,high);

QSort(L,low,pivot-1);

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

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

1,L.length

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

256，301，751，129，937，863，742，694，076，438快速排序第1趟第2趟第3趟第4趟256，301，751，129，937，863，742，694，076，438076，129，256，751，937，863，742，694，301，438要求模擬算法實(shí)現(xiàn)步驟256076301129751256076，129，256，438，301，694，742，694，863，937751076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742，751，863，937438076，129，256，301，438，694，742，751，863，937時(shí)間效率：O(nlog2n)—因?yàn)槊刻舜_定的元素呈指數(shù)增加空間效率：O（log2n）—因?yàn)樗惴ǖ倪f歸性，要用到?？臻g穩(wěn)定性：

不穩(wěn)定—因?yàn)榭蛇x任一元素為支點(diǎn)。43PPT課件例3：以關(guān)鍵字序列（256，301，751，129，937，快速排序算法詳細(xì)分析：可以證明，函數(shù)quicksort的平均計(jì)算時(shí)間也是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計(jì)算時(shí)間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個(gè)?？焖倥判蚴沁f歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)（新的low和high）。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為log2(n+1)

。因此，要求存儲(chǔ)開銷為o(log2n)。最好情況：如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對(duì)兩個(gè)長度減半的子序列進(jìn)行排序，這是最理想的情況。此時(shí)，快速排序的趟數(shù)最少。44PPT課件快速排序算法詳細(xì)分析：可以證明，函數(shù)quicksort的平均最壞情況：即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列。這樣，必須經(jīng)過n-1

趟才能把所有對(duì)象定位，而且第i

趟需要經(jīng)過n-i

次關(guān)鍵碼比較才能找到第

i

個(gè)對(duì)象的安放位置，總的關(guān)鍵碼比較次數(shù)將達(dá)到n2/2

快速排序是一個(gè)不穩(wěn)定的排序方法45PPT課件最壞情況：即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況討論2.

“快速排序”是否真的比任何排序算法都快？設(shè)每個(gè)子表的支點(diǎn)都在中間（比較均衡），則：第1趟比較，可以確定1個(gè)元素的位置；第2趟比較（2個(gè)子表），可以再確定2個(gè)元素的位置；第3趟比較（4個(gè)子表），可以再確定4個(gè)元素的位置；第4趟比較（8個(gè)子表），可以再確定8個(gè)元素的位置；

……只需log2n

＋1趟便可排好序?！旧鲜?！因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的！而且，每趟需要比較和移動(dòng)的元素也呈指數(shù)下降，加上編程時(shí)使用了交替逼近技巧，更進(jìn)一步減少了移動(dòng)次數(shù)，所以速度特別快。教材P276有證明：快速排序的平均排序效率為O(nlog2n)；但最壞情況(例如已經(jīng)有序)下仍為O(n2),改進(jìn)措施見P277。46PPT課件討論2.“快速排序”是否真的比任何排序算法都快？設(shè)每個(gè)子表10.4選擇排序選擇排序有多種具體實(shí)現(xiàn)算法：

1)簡(jiǎn)單選擇排序

2)錦標(biāo)賽排序

3)堆排序選擇排序的基本思想是：每一趟在后面n-i

個(gè)待排記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個(gè)記錄。47PPT課件10.4選擇排序選擇排序有多種具體實(shí)現(xiàn)算法：選擇排序的1）簡(jiǎn)單選擇排序思路簡(jiǎn)單：每經(jīng)過一趟比較就找出一個(gè)最小值，與待排序列最前面的位置互換即可?！紫?，在n個(gè)記錄中選擇最小者放到r[1]位置；然后，從剩余的n-1個(gè)記錄中選擇最小者放到r[2]位置；…如此進(jìn)行下去，直到全部有序?yàn)橹?。?yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：每趟只能確定一個(gè)元素，表長為n時(shí)需要n-1趟前提：順序存儲(chǔ)結(jié)構(gòu)

48PPT課件1）簡(jiǎn)單選擇排序思路簡(jiǎn)單：每經(jīng)過一趟比較就找出一個(gè)最小值，與例：關(guān)鍵字序列T=（21，25，49，25*，16，08），請(qǐng)給出簡(jiǎn)單選擇排序的具體實(shí)現(xiàn)過程。原始序列：

21，25，49，25*，16，08直接選擇排序第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2108，16,49，25*，25，2108，16,

21，25*，25，4908，16,

21，25*，25，4908，16,

21，25*，25，49時(shí)間效率：

O(n2)——雖移動(dòng)次數(shù)較少，但比較次數(shù)仍多?？臻g效率：O（1）——交換時(shí)用到一個(gè)暫存單元！算法的穩(wěn)定性：不穩(wěn)定——因?yàn)榕判驎r(shí)，25*到了25的前面。最小值08

與r[1]交換位置49PPT課件例：關(guān)鍵字序列T=（21，25，49，25*，16，08）簡(jiǎn)單選擇排序的算法如下：（亦可參見教材P276）VoidSelectSort(SqList&L

){for(i=1;i<L.length;++i){

j=SelectMinKey(L,i);if(i!=j)

r[i]r[j];}

}//SelectSort//對(duì)順序表L作簡(jiǎn)單選擇排序//選擇第i小的記錄，并交換到位//在r[i…L.length]中選擇key最小的記錄//與第i個(gè)記錄交換討論：能否利用（或記憶）首趟的n-1次比較所得信息，從而盡量減少后續(xù)比較次數(shù)呢？

答：能！請(qǐng)看——錦標(biāo)賽排序和堆排序！50PPT課件簡(jiǎn)單選擇排序的算法如下：（亦可參見教材P276）VoidS2）錦標(biāo)賽排序(又稱樹形選擇排序)基本思想：與體育比賽時(shí)的淘汰賽類似。

首先對(duì)n

個(gè)記錄的關(guān)鍵字進(jìn)行兩兩比較，得到n/2

個(gè)優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來。然后在這n/2

個(gè)較小者之間再進(jìn)行兩兩比較，…，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。優(yōu)點(diǎn)：減少比較次數(shù)，加快排序速度缺點(diǎn)：空間效率低例：關(guān)鍵字序列T=（21，25，49，25*，16，08，63），請(qǐng)給出錦標(biāo)賽排序的具體實(shí)現(xiàn)過程。51PPT課件2）錦標(biāo)賽排序(又稱樹形選擇排序)基本思想：與體育比賽08Winner(勝者)2108086325*2121254925*160863r[1]注：為便于自動(dòng)處理，建議每個(gè)記錄多開兩個(gè)特殊分量：初態(tài)：補(bǔ)足2k(k=log2n

)個(gè)葉子結(jié)點(diǎn)勝者樹第一趟：52PPT課件08Winner(勝者)2108086325*212125第二趟：082108086325*2121254925*160863161616r[2]Winner(勝者)求次小值16時(shí),只需比較2次，即只比較log2n-1次。令其Tag＝0,不參與比較53PPT課件第二趟：082108086325*2121254925*16令其Tag＝0,不參與比較第三趟：162116166325*2121254925*160863r[3]Winner(勝者)632154PPT課件令其Tag＝0,不參與比較第三趟：162116166325*082108086325*2121254925*1608636321第四趟：r[4]Winner(勝者)25252555PPT課件082108086325*2121254925*160863082108086325*2121254925*1608631616166321252525第五趟：r[5]Winner(勝者)25*25*56PPT課件082108086325*2121254925*160863082108086325*2121254925*160863161616632125252525*25*第六趟：r[6]Winner(勝者)49494957PPT課件082108086325*2121254925*160863082108086325*2121254925*160863161616632125252525*25*494949第七趟：r[7]Winner(勝者)6358PPT課件082108086325*2121254925*160863算法分析：錦標(biāo)賽排序構(gòu)成的樹是滿(完全）二叉樹，其深度為log2n+1，其中n

為待排序元素個(gè)數(shù)。時(shí)間復(fù)雜度：O(nlog2n)—n個(gè)記錄各自比較約log2n次空間效率：

O(n）—?jiǎng)僬邩涞母郊觾?nèi)結(jié)點(diǎn)共有n’-1個(gè)！穩(wěn)定性：穩(wěn)定—左右結(jié)點(diǎn)相同者左為先討論：在簡(jiǎn)單選擇排序過程中，每當(dāng)我們從表中選出最小元素之后，再選次最小元素時(shí)，必須把表中剩余元素再掃描一次。這樣，同一個(gè)元素會(huì)被掃描多次，浪費(fèi)！能否利用上次掃描的結(jié)果定出下一次的選擇結(jié)果呢？

答：能！請(qǐng)看——堆排序算法n’=2k=葉子總數(shù)59PPT課件算法分析：錦標(biāo)賽排序構(gòu)成的樹是滿(完全）二叉樹，其深度為3）堆排序1.什么是堆？堆的定義：設(shè)有n個(gè)元素的序列k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。ki≤

k2iki≤

k2i+1ki≥

k2iki≥

k2i+1或者i=1,2,…n/2解釋：如果讓滿足以上條件的元素序列（k1，k2，…，kn）順次排成一棵完全二叉樹，則此樹的特點(diǎn)是：樹中所有結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹的根結(jié)點(diǎn)（即堆頂）必最大（或最?。?。2.怎樣建堆？3.怎樣堆排序？60PPT課件3）堆排序1.什么是堆？堆的定義：設(shè)有n個(gè)元素的序列k082546495867234561（大根堆）918566765867234561557例：有序列T1=（08,25,49,46,58,67）和序列T2=（91,85,76,66,58,67,55）,判斷它們是否“堆”？√（小根堆）√（小頂堆）（最小堆）（大頂堆）（最大堆）61PPT課件082546495867234561（大根堆）9185667步驟：從最后一個(gè)非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個(gè)雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。212525*491608123456例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請(qǐng)建大根堆。2.怎樣建堆？解：為便于理解，先將原始序列畫成完全二叉樹的形式：完全二叉樹的第一個(gè)非終端結(jié)點(diǎn)編號(hào)必為n/2

！！(性質(zhì)5)注：終端結(jié)點(diǎn)（即葉子）沒有任何子女，無需單獨(dú)調(diào)整。21i=3:49大于08，不必調(diào)整；i=2:25大于25*和16，也不必調(diào)整；i=1:21小于25和49，要調(diào)整！49而且21還應(yīng)當(dāng)向下比較??！62PPT課件步驟：從最后一個(gè)非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個(gè)雙親大于（VoidHeapAdjust(HeapType&H,ints,intm){//rc=H.r[s];for(j=2*s;j<=m;j*=2)//沿key較大的孩子結(jié)點(diǎn)向下篩選

{if(j<m&<(H.r[j].key,H.r[j+1].key))++j;//j為key較大的記錄的下標(biāo)

if(!LT(rc.key,H.r[j].key))break;//rc應(yīng)插入在位置s上

H.r[s]=H.r[j];s=j;}H.r[s]=rc;//插入

}63PPT課件VoidHeapAdjust(HeapType&H,i關(guān)鍵：將堆的當(dāng)前頂點(diǎn)輸出后，如何將剩余序列重新調(diào)整為堆？方法：將當(dāng)前頂點(diǎn)與堆尾記錄交換，然后仿建堆動(dòng)作重新調(diào)整，如此反復(fù)直至排序結(jié)束。3.怎樣進(jìn)行堆排序？64PPT課件關(guān)鍵：將堆的當(dāng)前頂點(diǎn)輸出后，如何將剩余序列重新調(diào)整為堆？3.08252125*1649交換1號(hào)與6號(hào)記錄492525*21160812345649252125*1608初始最大堆2525*16211365420849例：對(duì)剛才建好的大根堆進(jìn)行排序：65PPT課件08252125*1649交換1號(hào)與61625*21082549交換1號(hào)與5號(hào)記錄08

252125*1649從1號(hào)到5號(hào)重新調(diào)整為最大堆082525*2116491234561625*08252149136542082525*2508

2125*1649082525*21

08164966PPT課件1625*21082549交換1號(hào)與508162125*2549交換1號(hào)與4號(hào)記錄25*1621082549從1號(hào)到4號(hào)重新調(diào)整為最大堆25*1608212549123456081625*25214913654267PPT課件08162125*2549交換1號(hào)與08162125*2549交換1號(hào)與3號(hào)記錄21160825*2549從1號(hào)到3號(hào)重新調(diào)整為最大堆211625*082549123456081625*25214913654268PPT課件08162125*2549交換1號(hào)與308162125*2549交換1號(hào)與2號(hào)記錄160821

25*2549從1號(hào)到2號(hào)重新調(diào)整為最大堆160825*212549123456081625*25214913654269PPT課件08162125*2549交換1號(hào)與2voidHeapSort(HeapType&H){//對(duì)順序表H進(jìn)行堆排序

for(i=H.length/2;i>0;--i)

HeapAdjust(H,i,H.length);//初始堆

for(i=H.length;i>1;--i){

H.r[1]H.r[i]; //交換，要借用tempHeapAdjust(H,1,i-1);//重建最大堆

}}堆排序的算法參見教材P281-282這是針對(duì)結(jié)點(diǎn)i的堆調(diào)整函數(shù)（也是建堆函數(shù)），每次調(diào)用耗時(shí)O(log2n)70PPT課件voidHeapSort(HeapType&H){附1：基于初始堆進(jìn)行堆排序的算法步驟：堆的第一個(gè)對(duì)象V[0]具有最大的關(guān)鍵碼，將V[0]與V[n]對(duì)調(diào)，把具有最大關(guān)鍵碼的對(duì)象交換到最后，再對(duì)前面的n-1個(gè)對(duì)象，使用堆的調(diào)整算法，重新建立堆。結(jié)果具有次最大關(guān)鍵碼的對(duì)象又上浮到堆頂，即V[0]位置。再對(duì)調(diào)V[0]和V[n-1]，調(diào)用對(duì)前n-2個(gè)對(duì)象重新調(diào)整，…如此反復(fù)，最后得到全部排序好的對(duì)象序列。71PPT課件附1：基于初始堆進(jìn)行堆排序的算法步驟：堆的第一個(gè)對(duì)象V[0]比較左右孩子大小，j指向大者比較大孩子與rc的大小若大向上浮rc=H.r[s];j=2s;j<m&&H.r[j].key<H.r[j+1].key++j;//指向右兄弟j<mrc.key>H.r[j].keyH.r[s]=H.r[j];s=j;j=2*j;//指向左孩子NNNYYYH.r[s…m]中除r[s]外，其他具有堆特征現(xiàn)調(diào)整r[s]的值，使H.r[s…m]為堆附2：

算法流程72PPT課件比較左右孩子大小，j指向大者比較大孩子與rc的大小rc=堆排序算法分析：時(shí)間效率：

O(nlog2n)。因?yàn)檎麄€(gè)排序過程中需要調(diào)用n-1次HeapAdjust()算法，而算法本身耗時(shí)為log2n；空間效率：O(1)。僅在第二個(gè)for循環(huán)中交換記錄時(shí)用到一個(gè)臨時(shí)變量temp。穩(wěn)定性：不穩(wěn)定。優(yōu)點(diǎn)：對(duì)小文件效果不明顯，但對(duì)大文件有效。73PPT課件堆排序算法分析：時(shí)間效率：O(nlog2n)。因?yàn)檎麄€(gè)排序10.5歸并排序歸并排序的基本思想是：將兩個(gè)（或以上）的有序表組成新的有序表。更實(shí)際的意義：可以把一個(gè)長度為n的無序序列看成是n個(gè)長度為1的有序子序列，首先做兩兩歸并，得到n/2個(gè)長度為2的子序列；再做兩兩歸并，…，如此重復(fù)，直到最后得到一個(gè)長度為n的有序序列。例：關(guān)鍵字序列T=（21，25，49，25*，93，62，72，08，37，16，54），請(qǐng)給出歸并排序的具體實(shí)現(xiàn)過程。74PPT課件10.5歸并排序歸并排序的基本思想是：將兩個(gè)（或以上）的212525*9362720837165449212525*4962930872163754163754212525*490862729308212525*496272930816212525*374954627293len=1len=2len=4len=8len=16163754整個(gè)歸并排序僅需log2n趟75PPT課件212525*9362720837165449212525*一趟歸并排序算法:(兩路有序并為一路)

參見教材P283void

Merge

(SR，&TR，i,m,n){//將有序的SR[i…m]和SR[m+1…n]歸并為有序的TR[i…n]for(k=i,j=m+1;i<=m&&j<=n;++k){if(SR[i]<=SR[j])TR[k]=SR[i++];elseTR[k]=SR[j++];//將SR中記錄由小到大地并入TR}if(i<=m)TR[k…n]=SR[i…m];//將剩余的SR[i…m]復(fù)制到TRif(j<=n)TR[k…n]=SR[j…n];//將剩余的SR[j…n]復(fù)制到TR}//Merge76PPT課件一趟歸并排序算法:(兩路有序并為一路)參見教材Pvoid

MSort(SR，&TR1，s,t){//將無序的SR[s…t]歸并排序?yàn)門R1[s…t]

if(s==t)TR1[s]=SR[s];//當(dāng)len=1時(shí)返回

else{

m=(s+t)/2;//將SR[s…t]平分為SR[s…m]和SR[m+1…t]

MSort(SR，&TR2，s,m);//將SR一分為二,2分為4…

//遞歸地將SR[s…m]歸并為有序的TR2[s…m]

MSort

(SR，&TR2，m+1,t);//遞歸地將SR[m+1…t]歸并為有序的TR2[m+1…t]

Merge(TR2，TR1，s,m,t);//將TR2[s…m]和TR2[m+1…t]歸并到TR1[s…t]

}

}//MSort遞歸形式的兩路歸并排序算法:參見教材P284

(一路無序變?yōu)橛行?簡(jiǎn)言之，先由“長”無序變成“短”有序，再從“短”有序歸并為“長”有序。初次調(diào)用時(shí)為（L,L,1,length）77PPT課件voidMSort(SR，&TR1，s,t){遞歸歸并排序算法分析：

時(shí)間效率：

O(nlog2n)一趟歸并排序的操作是：調(diào)用[n/2h]次算法merge將SR[1..n]中前后相鄰且長度為h的有序段進(jìn)行兩兩歸并，得到前后相鄰長度為2h的有序段，并存放在TR[1..n]中，整個(gè)歸并排序需要進(jìn)行[log2n]趟，所以算法總的時(shí)間復(fù)雜度為O(nlog2n)?？臻g效率：

O(n)因?yàn)樾枰粋€(gè)與原始序列同樣大小的輔助序列（TR）。這正是此算法的缺點(diǎn)。穩(wěn)定性：穩(wěn)定78PPT課件歸并排序算法分析：時(shí)間效率：O(nlog2n)78PPT各種內(nèi)部排序按所采用的基本思想(策略)可分為：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。它們的基本策略分別是：1）

插入排序：依次將無序序列中的一個(gè)記錄，按關(guān)鍵字值的大小插入到已排好序一個(gè)子序列的適當(dāng)位置，直到所有的記錄都插入為止。具體的方法有：直接插入、表插入、2-路插入和shell排序。2）

交換排序：對(duì)于待排序記錄序列中的記錄，兩兩比較記錄的關(guān)鍵字，并對(duì)反序的兩個(gè)記錄進(jìn)行交換，直到整個(gè)序列中沒有反序的記錄偶對(duì)為止。具體的方法有：冒泡排序、快速排序。各種內(nèi)部排序方法的比較

(教材P289）79PPT課件各種內(nèi)部排序按所采用的基本思想(策略)可分為：各種內(nèi)部排序方3）

選擇排序：不斷地從待排序的記錄序列中選取關(guān)鍵字最小的記錄，放在已排好序的序列的最后，直到所有記錄都被選取為止。具體的方法有：簡(jiǎn)單選擇排序、堆排序。4）

歸并排序：利用“歸并”技術(shù)不斷地對(duì)待排序記錄序列中的有序子序列進(jìn)行合并，直到合并為一個(gè)有序序列為止。5）基數(shù)排序：按待排序記錄的關(guān)鍵字的組成成分(“位”)從低到高(或從高到低)進(jìn)行。每次是按記錄關(guān)鍵字某一“位”的值將所有記錄分配到相應(yīng)的桶中，再按桶的編號(hào)依次將記錄進(jìn)行收集，最后得到一個(gè)有序序列。各種內(nèi)部排序方法的比較

(教材P289）80PPT課件3）選擇排序：不斷地從待排序的記錄序列中選取關(guān)鍵字最小的記各種內(nèi)部排序方法的比較

(教材P289）81PPT課件各種內(nèi)部排序方法的比較(教材P289）81PPT課件討論：若初始記錄基本無序，則選用哪些排序方法比較適合？若初始記錄基本無序，則最好選用哪些排序方法？答：對(duì)基本有序的情況，可選用直接插入、堆排序、冒泡排序、歸并排序等方法；

在基本無序的情況下，最好選用快速排序、希爾排序。82PPT課件討論：若初始記錄基本無序，則選用哪些排序方法比較適合？若初始數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容83PPT課件數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1PPT課件10.1概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序第10章內(nèi)部排序84PPT課件10.1概述第10章內(nèi)部排序2PPT課件10.1概述1.什么是排序？將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序

——便于查找！

85PPT課件10.1概述1.什么是排序？2.排序的目的是什么？10.1概述3.排序算法的好壞如何衡量？時(shí)間效率——排序速度（即排序所花費(fèi)的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小若排序算法所需的輔助空間不依賴問題的規(guī)模n，即空間復(fù)雜度是O(1)，則稱排序方法是就地排序，否則是非就地排序。穩(wěn)定性——若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。

86PPT課件10.1概述3.排序算法的好壞如何衡量？4PPT課件4.什么叫內(nèi)部排序？什么叫外部排序？

——若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；內(nèi)部排序基本操作有兩種：◆比較兩個(gè)關(guān)鍵字的大??；(比不可少的操作)◆存儲(chǔ)位置的移動(dòng)?！舸判蛴涗浺徊糠衷趦?nèi)存，一部分在外存，則稱為外部排序。注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時(shí)放入外存，顯然外部排序要復(fù)雜得多。

87PPT課件4.什么叫內(nèi)部排序？什么叫外部排序？——若待排序記錄都5.待排序記錄在內(nèi)存中怎樣存儲(chǔ)和處理？處理方式：①順序排序——數(shù)據(jù)間的邏輯順序關(guān)系通過其物理存儲(chǔ)位置的相鄰來體現(xiàn)，排序時(shí)直接移動(dòng)記錄；

適合數(shù)據(jù)較少的情況?、阪湵砼判颉獢?shù)據(jù)間的邏輯順序關(guān)系通過結(jié)點(diǎn)中的指針體現(xiàn)，排序時(shí)只修改指針，不移動(dòng)數(shù)據(jù)；③地址排序——數(shù)據(jù)存儲(chǔ)在一段連續(xù)地址的空間，構(gòu)造一個(gè)輔助表保持各數(shù)據(jù)的存放地址（指針），排序時(shí)先修改輔助表中的地址，最后再移動(dòng)記錄。

②③適合數(shù)據(jù)較多的情況!88PPT課件5.待排序記錄在內(nèi)存中怎樣存儲(chǔ)和處理？處理方式：6PPT課件注：大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的(便于直接移動(dòng)元素)6.順序存儲(chǔ)（順序表）的抽象數(shù)據(jù)類型如何表示？Typedefstruct{//定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu)

KeyTypekey;//關(guān)鍵字

InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RecordType;Typedefstruct{//定義順序表的結(jié)構(gòu)

RecordTyper[MAXSIZE+1];//存儲(chǔ)順序表的向量

//r[0]一般作哨兵或緩沖區(qū)

intlength;//順序表的長度}SqList;#defineMAXSIZE20//設(shè)記錄不超過20個(gè)typedefintKeyType;//設(shè)關(guān)鍵字為整型量（int型）89PPT課件注：大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的(便于直接移動(dòng)元素)67.內(nèi)部排序的算法有哪些？——按排序的規(guī)則不同，可分為5類：插入排序交換排序（重點(diǎn)是快速排序）選擇排序歸并排序基數(shù)排序d＝關(guān)鍵字的位數(shù)(長度)——按排序算法的時(shí)間復(fù)雜度不同，可分為3類：簡(jiǎn)單的排序算法：時(shí)間效率低，O(n2)先進(jìn)的排序算法:時(shí)間效率高，O(nlog2n)基數(shù)排序算法：時(shí)間效率高，O(d×n)90PPT課件7.內(nèi)部排序的算法有哪些？——按排序的規(guī)則不同，可分為510.2插入排序插入排序的基本思想是：插入排序有多種具體實(shí)現(xiàn)算法：

1)直接插入排序

2)折半插入排序

3)2路插入排序

4)希爾排序

每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大