數(shù)據(jù)結(jié)構(gòu)與算法之內(nèi)排序.ppt

《數(shù)據(jù)結(jié)構(gòu)與算法之內(nèi)排序.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。

1、7內(nèi)排序主要內(nèi)容內(nèi)部排序/外部排序穩(wěn)定/不穩(wěn)定排序排序算法性能分析內(nèi)部排序算法2內(nèi)排序設(shè)n個記錄的序列為{R1,R2,R3,...,Rn}其相應(yīng)的關(guān)鍵字序列為{K1,K2,K3,...,Kn}若規(guī)定1,2,3,...,n的一個排列p1,p2,p3,...,pn，使得相應(yīng)的關(guān)鍵字滿足如下非遞減關(guān)系:Kp≤Kp≤Kp≤...≤Kp123n則原序列變?yōu)橐粋€按關(guān)鍵字有序的序列:Rp,Rp,Rp,...,Rp123n{}此操作過程稱為排序。排序3內(nèi)排序內(nèi)部排序:指的是待排序記錄存放在計算機(jī)隨機(jī)存儲器中進(jìn)行的排序過程。外部排序

2、:指的是待排序記錄的數(shù)量很大，以致內(nèi)存一次不能容納全部記錄，在排序過程中尚需對外存進(jìn)行訪問的排序過程。內(nèi)部排序與外部排序4內(nèi)排序假設(shè)Ki=Kj，且排序前序列中Ri領(lǐng)先于Rj；若在排序后的序列中Ri仍領(lǐng)先于Rj，則稱排序方法是穩(wěn)定的。若在排序后的序列中Rj仍領(lǐng)先于Ri，則稱排序方法是不穩(wěn)定的。例，序列3158869若排序后得3688915穩(wěn)定的若排序后得3688915不穩(wěn)定的穩(wěn)定排序與不穩(wěn)定排序5內(nèi)排序排序的時間復(fù)雜性排序過程主要是對記錄的排序碼進(jìn)行比較和記錄的移動過程。因此排序的時間復(fù)雜性可以算法執(zhí)行中的數(shù)據(jù)比較次

3、數(shù)及數(shù)據(jù)移動次數(shù)來衡量。當(dāng)一種排序方法使排序過程在最壞或平均情況下所進(jìn)行的比較和移動次數(shù)越少，則認(rèn)為該方法的時間復(fù)雜性就越好，分析一種排序方法，不僅要分析它的時間復(fù)雜性，而且要分析它的空間復(fù)雜性、穩(wěn)定性和簡單性等。6內(nèi)排序按照排序過程中所依據(jù)的原則的不同可以分類為:插入排序交換排序選擇排序歸并排序基數(shù)排序二叉排序樹排序內(nèi)部排序7內(nèi)排序思想:利用有序表的插入操作進(jìn)行排序有序表的插入:將一個記錄插入到已排好序的有序表中，從而得到一個新的有序表。例，序列132738657697插入4913273849657697插入排序

4、——直接插入排序8內(nèi)排序例，序列49386597761327初始，S={49}；{3849}初始，令第1個元素作為初始有序表；依次插入第2,3,…,k個元素構(gòu)造新的有序表；直至最后一個元素；{384965}{38496597}{3849657697}{133849657697}{13273849657697}直接插入排序算法主要應(yīng)用比較和移動兩種操作。直接插入排序算法描述9內(nèi)排序voidinsertsort(ElemTypeR[],intn)//待排序元素用一個數(shù)組R表示，數(shù)組有n個元素{for(inti=1;i<

5、n;i++)//i表示插入次數(shù)，共進(jìn)行n-1次插入{ElemTypetemp=R[i];//把待排序元素賦給tempintj=i-1;while((j>=0)&&(temp

6、1Mmin=2（n-1）Cmax=1+2+…+n-1=（n2-n）/2Mmax=3+4+…+n+1=（n2+3n-4）/2Cave=（n2+n-2）/4Mave=（n2+5n-6）/4因此，直接插入排序的時間復(fù)雜度為O（n2）。直接插入算法的元素移動是順序的，該方法是穩(wěn)定的。11內(nèi)排序插入排序平均情況復(fù)雜度對每個i值，考慮平均情況下需要多少次比較。為簡化分析，假設(shè)所有的值是不相同的，對一個i和臨時變量x，x有i+1個位置可能會去012……….i-1x=A[i]比較次數(shù)和插入位置的關(guān)系：i=6A[0]A[1]A[2]

7、A[3]A[4]A[5]x=A[6]插入位置6543210比較次數(shù)123456612內(nèi)排序插入排序平均情況復(fù)雜度在對序列沒有其它任何信息的條件下,x到任何一個位置的概率都是1/(i+1).這樣,對一個特定的值i,需要的平均比較次數(shù)為:把所有n-1次插入累加起來,有:13內(nèi)排序由于直接插入排序算法利用了有序表的插入操作，故順序查找操作可以替換為折半(二分法)查找操作。例，序列49386597761327設(shè)已形成有序表{3849657697}13插入元素13折半插入排序leftrightmidrightmid01234

8、5right{}97766549381314內(nèi)排序算法:voidBinaryInsertSort(ElemTypeR[],intn){for(inti=1;i