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

第6章內(nèi)部分 Slide.1-術(shù)語和約定 速分類 并分類 分?jǐn)?shù)分類類0?

第6章內(nèi)部分 Slide.1-分類(Sorting)也叫排序(

。9 n,·7內(nèi)部分類(internalsorting)和外部類(externalsorting)分類E …X¨ 9?分類表

records{ key; other;recordsLIST[maxsize]第6章內(nèi)部分 Slide.1-對于給定數(shù)組 ¨4 A[1].key≤A[2].key≤……如果在分類之前存在 (1≤i＜j≤n >A[i]和A[j]分別被移至A[i1]和 ¨并且i1和滿足關(guān)0 6第6章內(nèi)部分 Slide.1- 0,· =

?,· ¨FI0 =0c W?–"r¨

,0c ?¨] =0c第6章內(nèi)部分 Slide.1- 比較關(guān)鍵字的次數(shù)—

1V¨b_

3交換記錄位置和移動記錄的次數(shù)—

& 3評價排序算法好壞的標(biāo) ①執(zhí)行時間和所需的輔助空②算法本身的復(fù)雜排序算法的空間復(fù)雜若排序算法所需的輔助空間并不依賴于問題的規(guī)模 ¨即輔助空間 ¨則稱之為就地排序 ceSou)非就地排序一般要求的輔助空間為O(n)（3）排序算法的時間開 … N¨,?Q決于輸入實例中

第6章內(nèi)部分 Slide.1- voidBubbleSort(intn,LISTA intx,yfor(i=1;i<=n-1;i++

f(n)=C3n+∑C2·(n-

2)for(j=n;j>=i+1;j--if(A[j].key<A[j-1]

當(dāng)n2≥1swap(A[j],A[j-}voidswap(x,records&x,records ww=x;x=y;y=w}

T(n)=O(f(n))=PEKAPEKAVS01234567

2)=voidInsertSort(intn,LISTA inti,jA[0].key=-∞for(i=1;i<=n;i++)

第6章內(nèi)部分 Slide.1-插入排序(Insertion Sort) _?,A ],F2 。while(A[j].key<A[j-1].key)

直接插入排序:假設(shè)待排序的記錄存放在 組 無序區(qū)為

?R[1] ?j?從i=2起直至 j!} T(n)=O(n2)

依次將R[i]插入當(dāng)前的有序區(qū)R[1..i- 生成含 。第6章內(nèi)部分 Slide.1-voidlnsertSort(intn,LIST //對表R中的記錄R[1..n]按遞增序進行插入intfor(i=2;i<=n；i++)//依次插入if(R[i].key<R[i-{j=i-1;//R[0] 且是Ri的副{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]的插入位R[j+1]=R[j]；//將關(guān)鍵字大于R[i].key的記錄后j--}while(R[0].key<R[j].key)；//當(dāng)Rikey≥Rjkey時終R[j+1]=R[0]；//Ri插入到正確的}?算法的時間性能分

第6章內(nèi)部分 Slide.1-對于具有 要進行n- 4/ │初始文件狀 正 反

│無序(平均 第i趟的關(guān)│1││（i-│字比較次│││││總關(guān)鍵字比較次 n- │(n+2)(n- │ │第i趟記錄移動次 │ │（i- │總的記錄移動次 │(n- │ │時間復(fù)雜 │ │ │ ?算法的空間復(fù)雜度分?直接插入排序的穩(wěn)定第6章內(nèi)部分 Slide.1- 于 ˙ x

?’ ′直至所取的增 - 第6章內(nèi)部分 Slide.1- void Pass(LISTR，int ?為當(dāng)前fori=d+1;i<=n；i+將R[d+1．．n]分別插入各組當(dāng)前的有序區(qū){j=i-d；//R[0] do{ R[j+d]=R[j]；//后移記錄j=j-d；//查找前一R[j+d]=R[0]；//插入R[i]到正確的位置}} 第6章內(nèi)部分 Slide.1-void Sort(LIST{do

不妨設(shè)increment=increment/3+1；//求下一增 Pass(R，increment)；//一趟增量為increment的 入排} 當(dāng)增量 Pass和 08$¨只是由于有哨兵而在內(nèi)循環(huán)中增加了一個循環(huán)判定條件 ¨以防下標(biāo)+|第6章內(nèi)部分 Slide.1-例如：關(guān)鍵字為493865977613274955增量序列為:5,13274955一趟結(jié)果 386597二趟結(jié)果 556597三趟結(jié)果:41327384949556576算法分 ?增量序列的選 ?G。 ①最后一個增量必須為②應(yīng)該盡量避免序列中的值(尤其是相鄰的值 第6章內(nèi)部分 Slide.1- WG,· n*l.25到1.6*n*1.25 {L2．S 排序的時間性能優(yōu)于直接插入排 -

pM0," 當(dāng) ?&和 即直接插入排序的最好時間復(fù)度O(n) 時間復(fù)雜度(n2) =③ ?G¨?6

J¨!4

-

后來增量

F9¨ ?E!¨<D′? F9¨ ?E!¨<D′? 9E?3<D′?_??。F第6章內(nèi)部分 Slide.1-1.線性選選最小的放在余下的n-1個中選項最小放重復(fù)直到結(jié)voidSelectSort(intn,LISTA inti,j，lowindexkeytypefor(i=1;i<n;{lowindex=i;lowkey=A[i].key;for(j=i+1;j<=n;i++)lowkey=A[j]lowindex=j}swap(A[i],A[lowindex])} T(n)=O(n2)

PEPEKAVS1234567第6章內(nèi)部分 Slide.1-voidsort(intn,int{intb[],i,for(i=0;i<n;for((i=0;i<n;for(j=0;j<n;if(a[i].key<a[j].key)

for(i=0;i<n;i++)for(j=0;j<n;j++)第6章內(nèi)部分 Slide.1-n把序列劃分 個子序列,不是完全平方,向上取值n(2)建立與每一個子序列相對應(yīng)的輔助工作單元,即二級存貯單元(3)利用線性選擇,分別找出各子序列的最小關(guān)鍵字存入二級單元4利用線性選擇在二級單元中找出最小的輸行5)(5)對全序列中具有最小單元的子序列,再次掃描,找出次小的送二級單元,再執(zhí)行(4)重復(fù)執(zhí)行45取盡為止.每次選擇后標(biāo)記例:F={8,7,2,5,4,6,9,1,3}共9個結(jié)點,劃分成3個子序2*4 74124第6章內(nèi)部分 Slide.1- 是分治策略(一般與遞歸技術(shù)結(jié)合使用)，以減少分類過程之中0?分解

N¨-

¨0 求解:

O則直接求組合

ˇL 第6章內(nèi)部分 Slide.1-設(shè)被分類的無序區(qū)為 >?文件 中的一個記錄(數(shù)據(jù)元素)的關(guān)鍵字v作為準(zhǔn)元素(控制關(guān)鍵字通過基準(zhǔn)元素v把表(文件,數(shù)據(jù)集合) @? 重復(fù) 6 9¨

>|； 9 61.掃描2.測試3.交第6章內(nèi)部分 Slide.1-9?

,·

? ? ?） &¨劃分次數(shù)為

¨全部比較次數(shù) ¨交換次數(shù)(n/6)log2n下標(biāo)kvA[i].key，A[(i+j)/2].keyA[j].key的中值

v=從A[i].key到

],·

=- =Ai] 第6章內(nèi)部分 Slide.1-/*設(shè)A是外部數(shù)組 FindPivot(inti,intj/*若 -(¨<返回 I¨左邊兩個不同關(guān)鍵字中的較大者的下標(biāo) intk

firstkey/*第1個關(guān)鍵字的值A(chǔ)[i].key/*從左到右查找不同的關(guān)鍵字fork=i+1;k<=jk*掃描不同的關(guān)鍵字ifA[k].keyfirstkey*選擇較大的關(guān)鍵字*/returnk;elseif(A[k].key<firstkeyreturni;return0;}第6章內(nèi)部分 Slide.1-、表的劃分(分割)掃描令游標(biāo)l從左端(初始時li¨直到遇到

¨越過關(guān)鍵字小于v的所有又令游標(biāo)r從右端(初始時r=j ¨越過關(guān)鍵字大于等于的所有記錄,直到遇到測試l和 若l<r,則轉(zhuǎn)(3 ¨否則(l>r,即l=r+1)轉(zhuǎn)(4 ¨轉(zhuǎn)(1)；(目的是使l和r都至少向其前進方向前此時A[i],…A[j]被劃分成為滿足條件的兩部分A[i],…A[l-1]和A[l],…,A[j]第6章內(nèi)部分 Slide.1-intPartition(inti,intj,keytypepivot/*劃分 ?G關(guān)鍵字≥pivot·{intl,r;

返回有子序列的起始下標(biāo)for(l=i;A[l].key<pivot;l++)for(r=j;A[l].key>=pivot;r--)if(l<r}while(l<=r l}

[i,……,j[i,…k-1,k,k+1,…j第6章內(nèi)部分 Slide.1-voidQuickSort(inti,intj/*對外部數(shù)組A的元素A[i],…,A[j]進行快速分類{keytypeintk;//關(guān)鍵字大于等于pivot的記錄在序列中的起始下標(biāo)intpivotindex;//關(guān)鍵字為pivot的記錄在數(shù)組A中的下標(biāo)pivotindex=FindPivot(i,j);ifpivotindex0//遞歸終止k=Partition(i,j,pivot);QuickSort(i,k-1);QuickSort(k,j);}}//對數(shù)組A[1],…,A[n]進行快速分類可調(diào)用QuickSort(1,n)實第6章內(nèi)部分 Slide.1-3v114v 26v5324v339v6v5533456591123345569556快速分類算法非遞歸

第6章內(nèi)部分 Slide.1-voidQuickSort(recordsR，intn{structintup;intstructstackinttop;elementdata;第6章內(nèi)部分 Slide.1-while(s->top!=0)/*棧不空,取一序列劃分 l=s->data[s-j=r;temp=R[i];/取第一個元素作為基準(zhǔn)dowhile(i<j&&R[j].key>=temp.key) whlie(i<j&&R[i].key<temp.key)i++;swap(R[j],R[i]);}while(i<=j第6章內(nèi)部分 Slide.1-ifi+1r*右序列多于2個記錄{s-s->data[s->top]s->data[s-}ifi-1l*左序列多于2個記錄{s-}為了不導(dǎo) 的劃分,選取基準(zhǔn)最好的方法是用一個隨函數(shù)產(chǎn)生一個位于I和J這間的隨機數(shù)K,有R[K]作為基準(zhǔn),相當(dāng)于強迫R[]中的記錄隨機分布第6章內(nèi)部分 Slide.1- ¨對長度為

情況是每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最 6<B6p˙,·0ZM0“,·jL$]A¨僅僅-比劃分前的無序區(qū)中 A0Z ¨快速排序必須做n- 6¨第i次劃分開始時區(qū)間長度為 ¨所需的比較次數(shù)為n-i(1≤i≤n- ： 61 那么當(dāng)文件的記錄已按遞增序(或遞減序 是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最 0

每次劃分所取的基準(zhǔn)¨則快速排序所需的比較2）最好時間復(fù)雜

第6章內(nèi)部分 Slide.1- ;¨每次劃分所取的基準(zhǔn)都是當(dāng)前無序區(qū)的"中值 1

W8$-1y遞歸樹的高度為

?$1j! ¨而遞歸樹每一層上結(jié)點所對應(yīng)的劃分過程中所需要的關(guān)鍵字比較次數(shù)總和不超過 ¨故整個序過程所需要的關(guān)鍵字比較總次數(shù)C(n)=O(nlogn , 空間復(fù)雜 )!B!Q j 其遞歸樹的高度為 ¨故遞歸后需?？臻g為 ;¨歸樹的高度為 ¨所需的棧空間為O(n)穩(wěn)定 ·如[2，2，1第6章內(nèi)部分 Slide.1- _ ?89 ?

L <2?,· ?&并 62? ? 自底向上和自頂向 ??設(shè)A[left],…,A[mid] A[mid+1],…,A[right]

。 ? 0§成一個分類B[left],

合并為一堆且有序 ?實現(xiàn)函數(shù) 第6章內(nèi)部分 Slide.1-voidMerge(intleft,intmid,intright,LISTA,LIST],…,,…,B[left intileft;jmid+1,kleft置初while(i<=mid&&j<=rightB[k++]=(A[i].key<=A[j].key)?A[i++]:A[j++]/*兩個序列非空時，取小者輸出到B[k]while(i<=mid B[k++]=A[i++]/*若第一個子序列非空(未處理完)， 剩余部分到Bwhile(j<=right B[k++]=A[j++]/*若第二個子序列非空(未處理完)， 剩余部分到B}時間復(fù)雜性：O(right－left＋1 空間復(fù)雜性：O(right－left＋1第6章內(nèi)部分 Slide.1-

共

Z¨將它們兩兩合并成n/2 每個序列長度為 最后一個序列長度為1）對n/2 ?；

j! {11} { 26 { 77 { 61 { 59 { 48{ 77 { 61}{ 48{ {

77}{ 48 77第6章內(nèi)部分 Slide.1-第1遍歸并的子序列長度為20，第2遍為21，…，第i遍為2i-1，所以由2i-，對于log2O(nlog2n)。子文件，故稱其為"二路歸并排序"。類似地有k(k>)路歸并排序后一個子序列的長度可能小于len，此時應(yīng)注意最后一個子序列的下第6章內(nèi)部分 Slide.1-當(dāng)子序列的個數(shù)為奇數(shù)時，則最后一個子序列無需與其它子序列歸并（輪空），直 到歸并序列之后即可總之，每遍歸并時，必須對子序列的個數(shù)是奇數(shù)、以及最后一個子序長度可能小于len兩種特殊情況進行特殊處理 {11} { 26 { 77 { 61 { 59 { 48{ 77 { 61}{ 48{ {

77}{ 48 77第6章內(nèi)部分 Slide.1-執(zhí)行一遍歸并的算法/*把A中長度為len的相鄰序列歸并成長度為2*len的序列的函數(shù)voidMpass(intn,intlen,LISTA,LIST/*把A中長度均為len的相鄰兩個分類子序列歸并入B，ｎ為A的記錄總數(shù){inti,tfor(i=1;i+2*len-1<=n;i+=2*lenMergei,i+len-1i+2*len-1AB);/*歸并長度為len的兩個分類子序列ifi+len-1n /*尚有兩個子序列，其中最后一個長度小于Mergeii+len-1nAB /*歸并最后兩個子序列 /*若i<=n且i+len-1>=n時，則剩余一個子序列輪空，直 for(t=i;t<=n;t++)B[ｔ]=A[ｔ]; /*Mpass第6章內(nèi)部分 Slide.1-voidSort(intn,LISTA /*二路歸并分類intlen1*當(dāng)前歸并子序列的長度，初始為1LISTBwhile(len<Mpass(n,len,A,B)len=2*lenMpass(nlenBA*A、B互換位置*/len=2*len;}}/*MergeSort第6章內(nèi)部分 Slide.1-自然歸并排序（naturalmergesort）是基本歸并排序的一種變化。它首先對輸入序列中已經(jīng)存在的有序子序列進行歸并。例如，元素序列4，8，3，7，1，5，6，2中包含有序的子序列[4，8]，3，7]，1，5，6]和[2]，這些子序列是按從左至右的順序?qū)υ乇磉M行掃描而產(chǎn)生的。（若位置i的元素比位置i1的元素大，則從位置i進行分割）對于上面這個元素序列，可找到四個子序列，子序列1和子序列2歸并可得[3478，子序列3和子序列4歸并可得1256，最后，歸并兩個子序列得到[1,2,3,4,5,6,7,8]。因此，對于上述元素序列， 需要進行[log2n]趟歸并。因此自然歸并排序?qū)⒃贠(n)的時間內(nèi)完成排序,而將普通歸并花費O(nlogn)的時間。自底向上的歸并算法效率較高，但可讀性差若采用分治技術(shù)自頂向下的算法，形式簡潔第6章內(nèi)部分 Slide.1-歸并分 算法思想(分治思想簡單地將原始序列劃分為兩個子分別對每個子序列遞歸排最后將排好序的子序列合并為一個有序序列，即歸并過步驟如果待排序的項數(shù)為0或1，返回對等的兩部分分別的遞將排好的兩部分歸并為一個有序第6章內(nèi)部分 Slide.1-第6章內(nèi)部分 Slide.1-分解：將當(dāng)前表區(qū)間一分為二，即 mid=(low+high)/2求解：遞歸地對表分區(qū)A[low],…,A[mid]和A[mid+1],…,進行歸并分類組合注意：遞歸的終止條件是子區(qū)間長度為1，因為一個記錄自然有序歸并分類的分治遞歸

第6章內(nèi)部分 Slide.1-voidSort(LISTA,LISTB,intlow,inthigh/*用分治法對A[low],…,A[high]進行二路歸并 intmid=(low+high)/2iflow<high*區(qū)間長度大1，high-low>0Sort(A,B,low,mid);Sort(A,B,mid+1,high);Merge(low,mid,hight,A,B)} /*Sort注：歸并分類是穩(wěn)定分類第6章內(nèi)部分 Slide.1-算法Sort的執(zhí)行過程如下圖所示的遞歸樹第6章內(nèi)部分 Slide.1-這棵歸并樹與快速排序類似,但會發(fā)現(xiàn)前而后者”分解”較難.時間復(fù)雜對長度為n的文件，需進行l(wèi)ogn趟二路歸并，每趟歸并的時間為 空間復(fù)雜需要一個輔助向量來暫存兩有序子文件歸并的結(jié)果，故其輔助間復(fù)雜度為第6章內(nèi)部分 Slide.1-一趟排序。一趟選出的關(guān)鍵字最小的記錄稱為“冠軍”，而“亞軍”是從與“冠軍”比較失敗的記錄中找出。輸出“冠軍”后，將（冠軍）第6章內(nèi)部分 Slide.1-對關(guān)鍵字序列72,73,71,23,94,16,05,68進行樹形選擇排第6章內(nèi)部分 Slide.1-“亞軍”是從與“冠軍”比較失敗的記錄中找出的∞第6章內(nèi)部分 Slide.1-例:一組待排序的記錄的關(guān)鍵字初始如下第一步

第6章內(nèi)部分 Slide.1-n個記錄的錦標(biāo)賽排序，每選擇一個記錄需缺點：需要較多的輔 與“最大值”進行多次多余的比較。對樹形排序的改進是

第6章內(nèi)部分 Slide.1-若2*i≤n，則A[i].keyA[2*i].key;A[2*i+1].key; 或(1若2*i≤n，A[i].key≥A[2*i].key

第6章內(nèi)部分 Slide.1- :,·K^= ??右兒子結(jié)點上的關(guān)?即A[ ]¨ ’f_[6‘ ˉ 。 ]

?,·ˉ6¨

。1 3 311233946112339465541592653第6章內(nèi)部分 Slide.1- ”

?8 G用完全二叉樹的數(shù) 結(jié)構(gòu)把數(shù)組所對應(yīng)的完全二叉樹以堆不斷擴

/j 令i=n/2,…,2,1分別把以n/2,…,2,1為根的完全二叉樹 即執(zhí)行算法PushDownin 6?令in,n1交換 ?, ?當(dāng)前最大的葉結(jié) 7,· ¨即執(zhí)行整理:把剩余的i- @即執(zhí)行PushDown(1,i- ;1],A[2],…,A[n] 按關(guān)鍵字有的數(shù)據(jù)集堆(按關(guān)鍵字有的數(shù)據(jù)集堆(建堆待分類數(shù)據(jù)集完二叉第6章內(nèi)部分 Slide.1-voidHeapSort(intn,LISTA intfor(i=n/2;i>=1;i /*初始建堆，從最右非葉結(jié)點開始 /*整理堆，把以i為根，最大下標(biāo)的葉為swap(A[1],A[i]);/*堆頂與當(dāng)前堆中的下標(biāo)最大的葉結(jié)點交換PushDown(1,i-/*整理堆把以1為根，最大葉下標(biāo)為i-1的完全二叉樹整理成堆}}T(n)=O(nlog2n第6章內(nèi)部分 Slide.1-四、整理堆算法：PushDown(first該操作的功能是把以Afirst為根，以Alast]為最后一個結(jié)點的完全二元樹整理A[first],…,A[last])具體操作如下子交換）。重復(fù)上述過程，直到以A[first]為根的完全二叉樹是堆為止。算法如下第6章內(nèi)部分 Slide.1-voidPushDown(intfirst,int intr=first; /*r是被下推到的適當(dāng)位置，初始值為根first*/while(r<=last/2)/*A[r]不是葉，否則是堆*/if((r==last/2)&& /*r有一個兒子在2*r上且為左兒子swap(A[r],A[2*r]);/*下推r=last/*循環(huán)結(jié)束

}第6章內(nèi)部分 Slide.1-else swap(A[r],A[2*r]);//與左兒子交換r=2*r;//下推到的位置}else r=2*r+1;/*下推到的位置也是下次考慮的根*/}else/*A[r]符合堆的定義，不必整理，循環(huán)結(jié)束O(log2(last/first))=O(log2

339253第6章內(nèi)部分 Slide.1-3392533434392655394653946553126565 393946551123394655 1

第6章內(nèi)部分 Slide.1-2 6第6章內(nèi)部分 Slide.1-五、時間復(fù)PutDown函數(shù)中，執(zhí)行一次while循環(huán)的時間是一個常數(shù)。因為r每次至少為原來的兩倍，假設(shè)while循環(huán)執(zhí)行次數(shù)為i，則當(dāng)r從first變?yōu)閒irst*2i時循環(huán)結(jié)束。此時r=first*2i>last/2ilog(last/first)-1)。所以while循環(huán)體最多執(zhí)行l(wèi)og2(last/first)次，即PushDown時間復(fù)雜性O(shè)(log(last/first))=Olog2n)?！郒eapSort時間復(fù)雜性O(shè)(nlog2六、不穩(wěn)定的，舉出反習(xí)題

第6章內(nèi)部分 Slide.1-54510840數(shù)據(jù)結(jié)構(gòu)的定義如下DP是一棵完全二元樹,它或是一空樹,或滿足下列情況:1.;2.若左子樹是小根堆;3.,若這樣的結(jié)點不存在則取j為右子樹中與i的父結(jié)點相對應(yīng)的結(jié)點結(jié)點i54510840問題:1.插入結(jié)點4的結(jié)果;2.描述插入新結(jié)點的算法第6章內(nèi)部分 Slide.1-6.5 理論上可以證明，對于基于關(guān)鍵字之間比較的分類，無論用什么方法至少需要進行l(wèi)og2n!次比較由Stirling 可知，log2n!。所以基于關(guān)鍵字比較的分類時間的下界是)此不存在時間復(fù)性低于此下界的基于關(guān)鍵字比較的分類!只有不通過關(guān)鍵字比較的分類方法,才有可能突破第6章內(nèi)部分 Slide.1-一、基數(shù)分類（時間復(fù)雜性可達到線性級（基數(shù)分類）。因此基數(shù)分類又稱為桶分類。顯然，要求關(guān)鍵字分量的取值范圍必須是有限的，否則可箱二、算法的基本不相同時取位數(shù)的最大值個分量，每個分量的值取值0,1,…,9,第6章內(nèi)部分 Slide.1-首先把全部數(shù)據(jù)裝入一個排隊 ¨然后按下列步驟進行初態(tài):設(shè)置 D 分配:依次從排隊中取出每個數(shù)據(jù) 第 data.key右第 ¨設(shè)其為到

¨把data插入排隊 ¨則全部數(shù)據(jù)被分 ?¨把每個數(shù)據(jù)插入排隊A。

¨并按照取重復(fù)

¨對于關(guān)鍵字中有figure位數(shù)字的數(shù)據(jù)進行 4*6¨即 ?,· 第6章內(nèi)部分 Slide.1-321 789 Q[8]:986987789 Q[9]:890 Q[9]: 890210321901432012123543765 901109210012018321123432543 987 018098109123310321432543678 890901 第6章內(nèi)部分 Slide.1- Radix(intk, p{intpower, Radix(intk, p{intpower,i;power=1;for(i=1;i<=p-1;i++power=power*10return((k%(power*10))/power)}{QueueQ[10];recordsdata;intpass,r,i;for(pass=1;pass<=figure;pass+)fori=0i<=9i++)/*置空隊列Makenull(Q[i])whileEmptyA*分配data=Front(A)DeQueue(A)for(i=0;i<=9;i++){}/*大大縮短收集操作的時間r=for(i=0;i<=9;i++){}/*大大縮短收集操作的時間fori=0i9i