數(shù)據(jù)結(jié)構(gòu) 第十章 排序

1第十章內(nèi)部排序本章目標(biāo)熟練掌握各內(nèi)部排序方法的基本思想；理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。掌握排序過程和實(shí)現(xiàn)算法；掌握各種排序方法時(shí)間復(fù)雜度的分析方法；了解各種排序方法的特點(diǎn)（比較和選擇）。10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數(shù)排序10.7

各種內(nèi)部排序方法的比較10.1概述所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。各科成績表；獎(jiǎng)學(xué)金評定綜合分；...？什么是排序？為什么排序？如何排序？內(nèi)部排序外部排序 將欲處理的記錄全部存放到內(nèi)存中排序，數(shù)據(jù)可被隨機(jī)存取插入式排序交換式排序選擇式排序待排序的記錄太多，不能同時(shí)存放內(nèi)存中，排序過程需要借助外存（比如：硬盤）來完成，記錄需要在內(nèi)存和外存間移動(dòng)。

排序的分類歸并排序基數(shù)排序比較標(biāo)準(zhǔn)穩(wěn)定性不穩(wěn)定性 排序過后能使關(guān)鍵字相等的記錄保持原順序中的相對位置 排序過后不能使關(guān)鍵字相等的記錄保持原順序中的相對位置49325649272732494956時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性排序算法的基本操作大多數(shù)排序算法都有兩個(gè)基本的操作：(1)比較兩條記錄的關(guān)鍵字(排序碼)大??；(2)移動(dòng)記錄本身或改變指向記錄的指針。

注意：

第(2)種基本操作的實(shí)現(xiàn)依賴于待排序記錄的存儲方式。據(jù)此可分為靜態(tài)排序和動(dòng)態(tài)排序。#defineMAXSIZE20

//順序表的最大長度typedefintKeyType;

//定義關(guān)鍵字類型為整數(shù)類型typedefstruct

{

KeyTypekey;

//關(guān)鍵字項(xiàng)

InfoTypeotherinfo;

//其他數(shù)據(jù)項(xiàng)}RedType；

//記錄類型typedefstruct{

RedTyper[MAXSIZE+1];

//r[0]閑置或作哨兵單元

intlength;

//順序表的當(dāng)前長度}SqList;

//順序表類型待排記錄的數(shù)據(jù)類型--順序存儲結(jié)構(gòu)10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數(shù)排序10.7

各種內(nèi)部排序方法的比較10.2

插入排序

2.

折半插入排序3.2-路插入排序4.表插入排序

1.直接插入排序5.希爾排序基本思想：（1）排序過程分步完成；（2）每步將一個(gè)待排序的記錄，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組記錄（有序序列）的適當(dāng)位置上；（3）通過若干步，便可將所有記錄全部插入，從而完成排序。通常，將這里的每個(gè)步驟稱為“趟”。1.直接插入排序基本操作：將一個(gè)待排序的記錄按其關(guān)鍵字的大小插入到前面已排好序的有序序列中。有序序列無序序列125786309412567830941.直接插入排序有序序列從只有一個(gè)記錄開始逐次增大；當(dāng)插入第i(i>=2)個(gè)記錄r[i]時(shí)，前面的r[1],r[2],…,r[i-1]已經(jīng)排好序。這時(shí)，用r[i]的關(guān)鍵字與r[i-1],r[i-2],…的關(guān)鍵字依次進(jìn)行比較，找到插入位置后將r[i]插入，原來位置上及以后的所有記錄順次向后移動(dòng)；當(dāng)有序序列大小最終和原始記錄集大小相同時(shí)排序完畢。1.直接插入排序[64]789624[564]89624[5764]624[576489]24[5676489][567246489]5789624初始序列:第一趟排序:第二趟排序:第三趟排序:第四趟排序:第五趟排序:Temp6j89j64j7j61.直接插入排序算法:voidInsertSort（SqList&L）{for(i=2;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-1].key){

L.r[0]=L.r[i];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];}}1.直接插入排序最壞情況下（逆序）：時(shí)間復(fù)雜度為O(n2)比較次數(shù)：移動(dòng)次數(shù)：2)1)(2(1-+=?=nn

(i+1)n-1i2)1)(4(2-+=+?nnin-11=i）（最好情況下（正序）：

比較次數(shù)：n-1移動(dòng)次數(shù)：0時(shí)間復(fù)雜度為O(n)性能分析:空間性能：需要一個(gè)記錄的輔助空間。直接插入排序算法是一種穩(wěn)定的排序算法。特點(diǎn)：簡單、容易實(shí)現(xiàn)，適用于待排序記錄基本有序或待排序記錄較少的情形。2.折半插入排序[5764]624[576489]24896第二次排序:第三次排序:Tfmp689647low6基本思想:在查找插入位置時(shí),使用折半查找算法。mhigh2.折半插入排序算法:voidBInsertSort(SqList&L){

for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;

while(low<=high){m=(low+high)/2;

ifLT(L.r[0].key,L.r[m].key)high=m-1;

elselow=m+1;}

for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];L.r[high+1]=L.r[0];}//for}//BInsertSort2.折半插入排序穩(wěn)定空間代價(jià)：O(1)時(shí)間代價(jià)：比較次數(shù)與待排記錄的初始順序無關(guān)，只依賴記錄個(gè)數(shù)插入每個(gè)記錄需要O(log2i)次比較

最多移動(dòng)i+1次，最少2次（臨時(shí)記錄）

最佳情況下總時(shí)間代價(jià)為O(nlog2n)，最差和平均情況下仍為O(n2)3.2-路插入排序基本思想：增設(shè)同類型數(shù)組d,視為循環(huán)向量。以d[1]為中心，原數(shù)列中比d[1]小的往前插，比d[1]大的往后插原數(shù)列：4938659776132749d數(shù)組：49d1firstfinal38first6597final76final13first27first9749finalvoidTwoWaySort(SqList&L){intfirst=1,final=1,i,j;RedTyped[MAXSIZE+1];//輔助存儲d[1].key=L.r[1].key;for(i=2;i<=L.length;i++){if(L.r[i].key>=d[1].key){//插入d1后for(j=final;d[j].key>L.r[i].key;j--)d[j+1].key=d[j].key;d[j+1].key=L.r[i].key;final++;}else{//插入d1前if(first==1){first=MAXSIZE-1;d[first].key=L.r[i].key;}else{for(j=first;d[j].key<L.r[i].key&&d[j].key&&j<MAXSIZE;j++)d[j-1].key=d[j].key;d[j-1].key=L.r[i].key;first--;}}}//forfor(i=first,j=1;L.r[j].key;i=i%(MAXSIZE-1)+1,j++)L.r[j].key=d[i].key;//將序列復(fù)制回去}4.希爾排序

基本思想：把待排序的數(shù)據(jù)元素分成若干個(gè)小組，對同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個(gè)數(shù)逐次縮?。划?dāng)完成了所有數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序后排序過程結(jié)束。希爾排序又稱作縮小增量排序。

4.希爾排序653425871238564614779223566514257787382356341477122365462587923865771234561214653423774625879238121423253438465665778792結(jié)果序列4.希爾排序voidShellInsert(SqList&L,intdk)

{

//1.前后記錄位置的增量是dk,而不是1;

//2.r[0]只是暫存單元,不是哨兵。當(dāng)j<=0時(shí),插入位置已找到。

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

if(LT(L.r[i].key,L.r[i-dk].key)){//需將L.r[i]插入有序增量子表L.r[0]=L.r[i];//暫存在L.r[0]for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//記錄后移，查找插入位置L.r[j+dk]=L.r[0];//插入}}4.希爾排序voidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]對順序表L作希爾排序。

for(k=0;k<t;++k)

ShellInsert(L,dlta[k]);//一趟增量為dlta[k]的插入排序}Gap的取法有多種。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。后來knuth提出取gap=gap/3+1。還有人提出都取奇數(shù)為好，也有人提出各gap互質(zhì)為好。10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數(shù)排序10.7

各種內(nèi)部排序方法的比較起泡排序基本思想：設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，循環(huán)進(jìn)行n-1趟如下的排序過程：依次比較相鄰兩個(gè)數(shù)據(jù)元素，若a[i]>a[i+1]，則交換兩個(gè)數(shù)據(jù)元素，否則不交換。當(dāng)完成一趟交換以后，最大的元素將會出現(xiàn)在數(shù)組的最后一個(gè)位置。依次重復(fù)以上過程，當(dāng)?shù)趎-1趟結(jié)束時(shí)，整個(gè)n個(gè)數(shù)據(jù)元素集合中次小的數(shù)據(jù)元素將被放置在a[1]中，a[0]中放置了最小的數(shù)據(jù)元素。起泡排序4938659776132749979797384927137665493849276513493849271349384927133827137676654949382713特點(diǎn)：1.n個(gè)數(shù)排序共需進(jìn)行n-1趟比較2.第i趟共需要進(jìn)行n-i次比較起泡排序的原始算法voidbubble_sort(SqList&L){//將a中整數(shù)序列排列成自小至大有序的序列(起泡排序)

for(i=1,i<=L.length-1;++i)for(j=1;j<=L.length-1;++j)if(LT(L.r[j+1].key,L.r[j].key))L.r[j]←→L.r[j+1]；}起泡排序的改進(jìn)算法（一）voidbubble_sort(SqList&L){//將a中整數(shù)序列排列成自小至大有序的序列(起泡排序)for(i=1;i<=L.length-1;++i)for(j=1;j<=L.length-i;++j)if(LT(L.r[j+1].key,L.r[j].key))L.r[j]←→L.r[j+1]}115246175115617524115617524161551724注意第i趟比較了n-i次，則可以有效的較少比較次數(shù)問題：剛才的改進(jìn)算法是否已經(jīng)最優(yōu)?起泡排序的改進(jìn)算法（二）123456789123456789123456789

123456789

分析：因?yàn)榻o定的待排序序列已經(jīng)是一個(gè)正序的序列，經(jīng)過第一趟的比較以后，已經(jīng)沒有交換發(fā)生，但是算法仍然會繼續(xù)執(zhí)行。解決：添加一個(gè)算法的結(jié)束條件，即當(dāng)某一趟排序過程中只有比較而沒有交換的時(shí)候，就認(rèn)定序列已經(jīng)有序，可以提前結(jié)束循環(huán)。起泡排序的改進(jìn)算法（二）voidbubble_sort(SqList&L){//將a中整數(shù)序列排列成自小至大有序的序列(起泡排序)for(i=1,chang=TRUE；(i<=L.length-1)&&chang;++i){chang=FALSE;for(j=1;j<L.length-i;++j)if(LT(L.r[j+1].key,L.r[j].key)){L.r[j]

←→L.r[j+1];

change=TRUE;}}}最壞情況（反序）：最好情況（正序）：比較次數(shù)：n-1移動(dòng)次數(shù)：0

時(shí)間復(fù)雜度為O(n)；時(shí)間復(fù)雜度為O(n2)。比較次數(shù)：移動(dòng)次數(shù)：2)1(1-=?=nn(n-i)n-1i2)1(1-=?=n3n3(n-i)n-1i平均情況：時(shí)間復(fù)雜度為O(n2)。時(shí)間性能分析快速排序算法思想：指定樞軸(通常為第一個(gè)記錄)通過一趟排序?qū)⒁詷休S為中心，把待排記錄分割為獨(dú)立的兩部分，使得左邊記錄的關(guān)鍵字小于樞軸值，右邊記錄的關(guān)鍵字大于樞軸值對左右兩部分記錄序列重復(fù)上述過程，依次類推，直到子序列中只剩下一個(gè)記錄或不含記錄為止?？焖倥判?938659776132749pivotkey=49lowhigh27low65high13low97highhigh49第一趟結(jié)果：[273813]49[76976549]小于49大于等于49快速排序算法

intPartition(SqList&L,intlow,inthigh){L.r[0]=L.r[low];//用子表的第一個(gè)記錄作樞軸記錄pivotkey=L.r[low].key;//樞軸記錄關(guān)鍵字

while(low<high){//從表的兩端交替地向中間掃描

while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//將比樞軸記錄小的記錄移到低端

while(low<high&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low];//將比樞軸記錄大的記錄移到高端}L.r[low]=L.r[0];//樞軸記錄到位

returnlow;//返回樞軸位置}快速排序算法

voidQSort(SqList&L,intlow,inthigh){//對順序表L中的//長度大于1

if(low<high){pivotloc=Partition(L,low,high);//將L.r[low..high]一分為二QSort(L,low,pivotloc-1);//對低子表遞歸排序，pivotloc是樞軸位置QSort(L,pivotloc+1,high);//對高子表遞歸排序

}}

voidQuickSort(SqList&L){//對順序表L作快速排序。算法10.8

QSort(L,1,L.length);}算法分析在n個(gè)元素的序列中，對一個(gè)對象定位所需時(shí)間為O(n)。若設(shè)t(n)是對n個(gè)元素的序列進(jìn)行排序所需的時(shí)間，而且每次對一個(gè)對象正確定位后，正好把序列劃分為長度相等的兩個(gè)子序列，此時(shí)，總的計(jì)算時(shí)間為：T(n)cn+2t(n/2) //c是一個(gè)常數(shù)cn+2(cn/2+2t(n/4))=2cn+4t(n/4)2cn+4(cn/4+2t(n/8))=3cn+8t(n/8)………cnlog2n+nt(1)=o(nlog2n)10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數(shù)排序10.7

各種內(nèi)部排序方法的比較直接選擇排序基本思想：從待排序的數(shù)據(jù)元素集合中選取最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個(gè)數(shù)據(jù)元素交換位置；然后從不包括第一個(gè)位置上數(shù)據(jù)元素的集合中選取最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第二個(gè)數(shù)據(jù)元素交換位置；如此重復(fù)，直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。直接選擇排序149238365497576613727849ki=1jkjjjjkjjk1349直接選擇排序149238365497576613727849i=kjjjjjj1349kk2voidSelectSort(SqList&L){for(inti=1;i<L.length;i++) k=SelectMinKey(L,i);if(i!=k)L.r[i]←→L.r[k];}voidSelectMinKey(SqList&L,constinti){intk=i; for(j=i+1;j<=L.length;j++)if(L.r[j].key<L.r[k].key) k=j;//當(dāng)前具最小關(guān)鍵碼的對象returnk; }直接選擇排序的算法最壞情況：3(n-1)次直接選擇排序算法的性能分析移動(dòng)次數(shù)：最好情況（正序）：0次比較次數(shù)：)()1(21211nOnninni=-=-?-=）（簡單選擇排序的時(shí)間復(fù)雜度為O(n2)。樹形選擇排序排序思想：首先取得n個(gè)對象的關(guān)鍵碼，進(jìn)行兩兩比較，得到n/2個(gè)比較的優(yōu)勝者(關(guān)鍵碼小者)，作為第一步比較的結(jié)果保留下來。然后對這n/2個(gè)對象再進(jìn)行關(guān)鍵碼的兩兩比較，…，如此重復(fù)，直到選出一個(gè)關(guān)鍵碼最小的對象為止。133813973865493876131327652749139749387613652749381338651327∞27382738657627279749387613652749382738657627∞13∞38384938657649算法分析除第一次選擇具有最小關(guān)鍵碼的對象需要進(jìn)行n-1次關(guān)鍵碼比較外，重構(gòu)勝者樹選擇具有次小、再次小關(guān)鍵碼對象所需的關(guān)鍵碼比較次數(shù)均為O(log2n)?？傟P(guān)鍵碼比較次數(shù)為O(nlog2n)。對象的移動(dòng)次數(shù)不超過關(guān)鍵碼的比較次數(shù)，故錦標(biāo)賽排序總的時(shí)間復(fù)雜度為O(nlog2n)這種排序方法雖然減少了許多排序時(shí)間，但是使用了較多的附加存儲。堆排序把待排序的數(shù)據(jù)元素集合構(gòu)成一個(gè)完全二叉樹結(jié)構(gòu)，則每次選擇出一個(gè)最大（或最?。┑臄?shù)據(jù)元素設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，數(shù)組下標(biāo)從0開始，如果當(dāng)數(shù)組下標(biāo)2i+1<n時(shí)有：a[i]≥a[2i+1]；如果當(dāng)數(shù)組下標(biāo)2i+2<n時(shí)有：a[i]≥a[2i+2]，則這樣的數(shù)據(jù)結(jié)構(gòu)稱為最大堆。性質(zhì)5（2）如果2×i+1<n，則序號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號為2×i+1；如果2×i+1≥n，則序號為i結(jié)點(diǎn)無左孩子結(jié)點(diǎn)。堆排序(續(xù))設(shè)數(shù)組a中存放了n個(gè)數(shù)據(jù)元素，數(shù)組下標(biāo)從0開始，如果當(dāng)數(shù)組下標(biāo)2i+1<n時(shí)有：a[i]≤a[2i+1]；如果當(dāng)數(shù)組下標(biāo)2i+2<n時(shí)有：a[i]≤a[2i+2]，則這樣的數(shù)據(jù)結(jié)構(gòu)稱為最小堆。9683273811091236248547913053堆排序基本思想：以初始關(guān)鍵字序列，建立堆；輸出堆頂最小元素；調(diào)整余下的元素，使其成為一個(gè)新堆；重復(fù)2,3步，直到n個(gè)元素輸出，得到一個(gè)有序序列。關(guān)鍵問題：如何由一個(gè)無序序列建成一個(gè)堆?如何調(diào)整余下的元素成為一個(gè)新堆?堆調(diào)整過程1338277697654949rc=13篩選過程voidHeapAdjust(SqListR[],ints,intm){

//已知R[s..m]中記錄的關(guān)鍵字除R[s].key之外均滿足堆的定義，本函數(shù)調(diào)整R[s]的關(guān)鍵字，使R[s..m]成為一個(gè)大頂堆rc=R[s];for(j=2*s;j<=m;j*=2){

//沿key較大的孩子結(jié)點(diǎn)向下篩選if(j<m&&R[j].key<R[j+1].key)++j;//j為key較大 //的記錄的下標(biāo)if(rc.key>=R[j].key)break;//rc應(yīng)插入在位置s上R[s]=R[j];s=j;}R[s]=rc;//插入}

//HeapAdjust建堆過程無序序列建堆過程

方法：從完全二叉樹的最后一個(gè)非葉結(jié)點(diǎn)

n/2開始，反復(fù)調(diào)用篩選過程，直到第一個(gè)結(jié)點(diǎn)，則得到一個(gè)堆。建堆算法voidHeapSort(SqListR[],intn){//對記錄序列R[1..n]進(jìn)行堆排序。

for(i=n/2;i>0;--i)//把R[1..n]建成大頂堆

HeapAdjust(R,i,n);

for(i=n;i>1;--i){R[1]←→R[i];//將堆頂記錄和當(dāng)前未經(jīng)排序子序列//R[1..i]中最后一個(gè)記錄相互交換

HeapAdjust(R,1,i-1);

}//將R[1..i-1]重新調(diào)整為大頂堆}//HeapSort性能分析對深度為k的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1);對n個(gè)關(guān)鍵字，建成深度為h(=log2n+1)的堆，所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為4n;調(diào)整“堆頂”n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過2(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)因此，堆排序的時(shí)間復(fù)雜度為O(nlogn)，不穩(wěn)定。10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數(shù)排序10.7

各種內(nèi)部排序方法的比較歸并排序基本思想：將一個(gè)具有n個(gè)待排序記錄的序列看成是n個(gè)長度為1的有序序列，然后進(jìn)行兩兩歸并，得到n/2個(gè)長度為2的有序序列，再進(jìn)行兩兩歸并，得到n/4個(gè)長度為4的有序序列，……，直至得到一個(gè)長度為n的有序序列為止。歸并排序過程<初態(tài)>(49)(38)(65)(97)(76)(13)(27)(3849)<第2趟>(38496597)(132776)<第3趟>(13273849657697)<第1趟>(6597)(1376)(27)歸并排序算法voidMerge(RedTypeSR[],RedType&TR[],inti,intm,intn){//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]intj,k,l;for(j=m+1,k=i;i<=m&&j<=n;++k)//將SR中記錄由小到大地并入TRifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];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}歸并排序算法(續(xù))voidMSort(RedTypeSR[],RedType&TR1[],ints,intt){//將SR[s..t]歸并排序?yàn)門R1[s..t]if(s==t)TR1[s]=SR[s];else{m=(s+t)/2;//將SR[s..t]平分為SR[s..m]和SR[m+1..t]MSort(SR,TR2,s,m);//遞歸地將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]}}voidMergeSort(SqList&L){//對順序表L作歸并排序。算法10.14MSort(L.r,L.r,1,L.length);}10.2

插入排序10.3

交換排序10.4

選擇排序10.1

概述10.5

歸并排序10.6

基數(shù)排序10.7

各種內(nèi)部排序方法的比較基數(shù)排序排序思想：基數(shù)排序是按組成關(guān)鍵字的各位的值進(jìn)行分配和收集，與前面介紹的排序方法不同，它無需進(jìn)行關(guān)鍵字之間的比較。設(shè)關(guān)鍵字有d位，每位的取值范圍為r(稱為基數(shù))，則需要進(jìn)行d趟分配與收集，需要設(shè)立r個(gè)隊(duì)列。例如，關(guān)鍵字是4位字符串，需要26個(gè)隊(duì)列，4趟分配與收集；關(guān)鍵字3位十進(jìn)制數(shù)，需要10個(gè)隊(duì)列，3趟分配與收集基數(shù)排序過程278—109—063—930—589—184—505—269—008—083f[0]f[1]f[2]f[3]

f[4]f[5]f[6]f[7]f[8]f[9]e[0]e[1]e[2]e[3]

e[4]e[5]e[6]e[7]e[8]e[9]278pp109p063p930p589p184p505p269p008p083930—063—083—184—505—278—008—109—589—269505—008—109—930—063—269—278—083—184—589f[0]f[1]f