程序設(shè)計(jì)培訓(xùn)講義5：排序與查找ppt課件

1、程序設(shè)計(jì)培訓(xùn)五排序與查找.一、順序查找基本思想： 從第一個(gè)元素或最后一個(gè)元素開始，逐個(gè)把數(shù)據(jù)元素的關(guān)鍵字值和給定值比較，若某個(gè)元素的關(guān)鍵字值和給定值相等，則查找成功。否則，若直至第n個(gè)數(shù)據(jù)元素都不相等，說(shuō)明不存在滿足條件的數(shù)據(jù)元素，查找失敗。 算法特點(diǎn)：算法簡(jiǎn)單，既適用于以順序存儲(chǔ)結(jié)構(gòu)組織的查找表的查找，也適用于以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)組織的查找表的查找；但執(zhí)行效率低。.#includeint search (int a, int n, int k) /*a查找表, n表長(zhǎng), k關(guān)鍵字*/ int i; for (i=0; in; i+) if (k=ai) return (i+1); return 0

2、; void main()int x,t，a9=10,31,12,42,35,76,16,18,29,; scanf(%d,&x);t=search(a,9,x);if (t=0) printf(Not found!n);else printf(%dn,t); ./改進(jìn)的順序查找#includeint search (int a, int n, int k) /*a查找表, n表長(zhǎng), k關(guān)鍵字*/ int i=n; a0=k; while (ai!=k) i-; return i; void main()int a10=0,10,31,12,42,35,76,16,18,29,;int x,t

3、;scanf(%d,&x);t=search(a,9,x);if (t=0) printf(Not found!n);else printf(%dn,t); .二、折半(二分)查找基本思想： 如果查找表中的數(shù)據(jù)元素按關(guān)鍵字有序（假設(shè)遞增有序），則在查找時(shí)，可不必逐個(gè)順序比較，而采用跳躍的方式先與“中間位置”的數(shù)據(jù)元素關(guān)鍵字比較，若相等，則查找成功；若給定值大于“中間位置”的關(guān)鍵字，則在查找表的后半部繼續(xù)進(jìn)行二分查找，否則在前半部進(jìn)行二分查找。 算法特點(diǎn)：僅適用于以順序存儲(chǔ)結(jié)構(gòu)組織有序表的查找。.先確定待查元素所在區(qū)域，然后逐步縮小區(qū)域，直到查找成功或失敗為止。 假設(shè)：待查元素所在區(qū)域的下界為l

4、ow，上界為hig，則中間位置mid=(low+hig)/2 1、若此元素關(guān)鍵字值等于給定值，則查找成功 2、若此元素關(guān)鍵字值大于給定值，則在區(qū)域 (mid+1)與high 內(nèi)進(jìn)行二分查找 3、若此元素關(guān)鍵字值小于給定值，則在區(qū)域low與(mid-1) 內(nèi)進(jìn)行二分查找./非遞歸算法int bin_search (int a , int n, int k) int low, high, mid; low=0; high=n-1; while (low = high) mid=(low + high)/2; if (k amid) low = mid + 1;else return mid ; r

5、eturn -1;./遞歸算法int bin_search (int a , int low,int high ,int k)int mid=(low + high)/2;if ( lowhigh) return -1;else if (k = amid) return mid; else if (k amid ) bin_search(a,mid+1,high,k); else bin_search(a,low,mid-1,k) ; .例1、2006年湖南人文科技學(xué)院預(yù)賽試題給定整數(shù) a1,a2,a3,an（其中有負(fù)數(shù)），求整數(shù)中的最大子序列和。為了方便起見，如果所有整數(shù)為負(fù)數(shù)，則最大子序列

6、和為0。例如：對(duì)于-2、11、-4、13、-5、-2，最大子序列和為20（11-4+13）。 方法1：二分法，時(shí)間復(fù)雜度為O（nlog2n）其余方法詳見： 程序設(shè)計(jì)培訓(xùn)講義7：數(shù)組.#include #define N 100int aN=-2,11,-4,13,-5,-2;int max3(int x,int y,int z)int m;m=xy ? x:y;return mz ? m :z;void main()int maxsub(int a,int left,int right);printf(Maxsub=%dn,maxsub(a,0,3); .int maxsub(int a ,i

7、nt left,int right)int i,mid,maxleft,maxright,m1,m2,max1,max2;if (left=right) if (aleft0) return aleft; else return 0;mid=(left+right)/2;maxleft=maxsub(a,left,mid);maxright=maxsub(a,mid+1,right);for (m1=0,max1=0,i=mid; i=left; i-)m1=m1+ai;if ( m1 max1 ) max1=m1; for (m2=0,max2=0,i=mid+1; i max2 ) max

8、2=m2; return max3(maxleft,maxright,max1+max2);.三、排序算法分類 插入排序類直接插入排序、折半插入排序、希爾排序選擇排序類直接選擇排序、樹型選擇排序、堆排序交換排序類冒泡排序（稱直接交換排序）、快速排序 歸并排序類二路歸并四、非遞歸排序算法.1、插入排序 把n個(gè)數(shù)據(jù)元素的序列分成兩部分： R1, ., Ri-1為已排好序的有序部分 Ri, Ri+1, ., Rn 為未排序部分 把未排序部分的第1個(gè)元素Ri依次與R1, ., Ri-1比較，并插入到有序部分的合適位置上，使得 R1, ., Ri 變?yōu)樾碌挠行虿糠帧?初始時(shí)，令i=2。因?yàn)橐粋€(gè)元素自然有

9、序，故R1 自然成為一個(gè)有序部分，未排序部分是R2, ., Rn，然后依次將R2, R3, ., Rn插入到有序部分中去，就可得整個(gè)有序序列.初始關(guān)鍵字: 49 38 65 97 76 13 27 49i=2: 38 49 65 97 76 13 27 49i=3: 38 49 65 97 76 13 27 49i=4: 38 49 65 97 76 13 27 49i=6: 13 38 49 65 76 97 27 49i=7: 13 27 38 49 65 76 97 49i=8: 13 27 38 49 49 65 76 97i=5: 38 49 65 76 97 13 27 49無(wú)序有

10、序.void insert(int a ,int n)/對(duì)數(shù)組a中的元素a1、a2an 排序int i,j;for (i=2; i=n; i+) if ( aiai-1 ) a0=ai;j=i-1;while (a0=1) for (i=d+1; i0 & a0aj) aj+d=aj; j=j-d; aj+d=a0; d=d/2;.3、直接選擇排序第一趟排序是在無(wú)序的R1, R2, R3, ., Rn按排序碼選出最小的元素，將它與R1交換。第二趟排序是在無(wú)序的R2, R3, ., Rn中選出最小的元素，將它與R2交換。第i趟排序時(shí)R1, R2, R3, ., Ri-1已排好序，在當(dāng)前無(wú)序的Ri

11、, ., Rn中再選出最小的元素，將它與Ri元素交換，使R1, R2, R3, ., Ri成為有序 經(jīng)過(guò)n-1趟排序后，整個(gè)數(shù)據(jù)元素序列就遞增有序。./直接選擇排序/對(duì)數(shù)組a中的元素a0、a1an-1 排序void sort(int a ,int n)int i, j, t, min;for (i=0; in-1; i+) min=i;/ 尋找當(dāng)前最小元素的下標(biāo)存入min for (j=i+1; jn;j+)if ( ajamin ) min=j; t=amin; amin=ai; ai=t; .4、冒泡排序 (直接交換排序) 第一趟每次進(jìn)行相鄰兩個(gè)元素關(guān)鍵字的比較，如不符合次序立即交換,這樣

12、關(guān)鍵值大的（或小的）就會(huì)象冒氣泡一樣逐步升起。 算法思想： 先將rn與rn-1比較，若rnrn-1則互相交換。 再比較rn-1和rn-2，依次類推，直到rt與r1比較（交換）把關(guān)鍵字較小的記錄移至最前，完成一趟排序。 然后對(duì)余下的r(2)r(n)的n-1個(gè)記錄重復(fù)上述操作。./冒泡排序1：大數(shù)向后移/對(duì)數(shù)組a中的元素a0、a1an-1 排序void sort(int a ,int n)int i, j, t;/大數(shù)向后移，外循環(huán)一次，/將當(dāng)前的最大數(shù)移到a10-i上for (i=0; in-1; i+) for (j=0; jaj+1 ) t=aj; aj=aj+1; aj+1=t; ./冒泡

13、排序2：小數(shù)向前移/對(duì)數(shù)組a中的元素a0、a1an-1 排序void sort(int a ,int n)int i, j, t;/ 小數(shù)向前移，外循環(huán)一次/ 將當(dāng)前的最小數(shù)移到ai上for (i=0; in-1; i+) for (j=i+1; jn;j+) if ( ajai ) t=aj; aj=ai; ai=t; ./冒泡排序3：改進(jìn)的冒泡排序/對(duì)數(shù)組a中的元素a0、a1an-1 排序void sort(int a ,int n)int i, j, t,bz=1;for (i=0; in-1 & bz; i+) bz=0; /表示不需要繼續(xù)排序 for (j=0; jaj+1 ) t=

14、aj; aj=aj+1; aj+1=t; bz=1; /*存在交換，需要繼續(xù)排序*/ ./冒泡排序4：改進(jìn)的冒泡排序/對(duì)數(shù)組a中的元素a0、a1an-1 排序void sort(int a ,int n)int k,j,t,m=n-1;while ( m0 )/小數(shù)向前移，將當(dāng)前的最小數(shù)移到ai上 for (k=j=0; jaj+1 ) t=aj; aj=aj+1; aj+1=t; k=j; /記下最后一次交換的元素的下標(biāo) 到km=k; /也可以為 m=m-1 .5、快速排序快速排序又稱分區(qū)交換排序，是對(duì)冒泡排序的一種改進(jìn)，是目前內(nèi)部排序中比較快的方法。它通過(guò)分步排序來(lái)完成整個(gè)表的排序。這種方

15、法的每一步都把要排序表的第一個(gè)元素（或者是中間位置的元素）放到它在表中的最終位置，同時(shí)在這個(gè)元素的前面和后面各形成一個(gè)子表。在前子表中的所有元素的關(guān)鍵字都比該元素的關(guān)鍵字小，而在后子表中的都比它大。此后再對(duì)每個(gè)子表做同樣的操作，直到最后每個(gè)子表都只有一個(gè)元素，排序結(jié)束.初始關(guān)鍵字序列:49 38 65 97 76 13 27 4949 38 65 97 76 13 27 4927 38 65 97 76 13 49 4927 38 49 97 76 13 65 4927 38 13 97 76 49 65 4927 38 13 49 76 97 65 49i1j1ij1i1i1j1i1j1i1

16、j1i1j1./快速排序1：以第1個(gè)元素來(lái)分區(qū)間/對(duì)數(shù)組a中的元素aleft、aleft+1aright 排序void sort(int a ,int left, int right) int i,j,t; i=left ; j=right; t=ai; do while ( t=aj & ij ) j-; /從后向前搜索 if ( ij ) ai=aj; i+; while ( ai=t & ij ) i+; /從前向后搜索 if ( ij ) aj=ai; j-; while (i!=j);ai=t; /把t即最先的ai放到此次的適當(dāng)位置if ( lefti ) qsort(a,i+1,r

17、ight); /排序后半部分./快速排序2：以中間元素來(lái)分區(qū)間/對(duì)數(shù)組a中的元素aleft、aleft+1aright 排序void sort(int a ,int left, int right) int i,j,x,y;i=left ; j=right; x=a(left+right)/2; /用中間元素 do while ( aix & ix & jleft ) j-; /找一個(gè)比x小的元素aj if ( i=j ) y=aj;aj=ai; ai=y; i+; j-; while (i=j); if ( lefti ) sort(a,i+1,right);/排序后半部分.6、歸并排序(表

18、排序)歸并的含義是把兩個(gè)（或兩個(gè)以上）有序的序列合并為一個(gè)有序的序列。將有n個(gè)元素的原始序列看作n個(gè)有序子序列，每個(gè)子序列的長(zhǎng)度為1然后從第一個(gè)子序列開始，把相鄰的子序列兩兩合并，得到n/2個(gè)長(zhǎng)度為2或1的子序列，這一過(guò)程稱為一次歸并排序。對(duì)第一次歸并排序后的n/2個(gè)子序列采用上述方法，繼續(xù)順序歸并，如此重復(fù)，當(dāng)最后得到長(zhǎng)度為n的一個(gè)子序列時(shí)，該子序列便是原始序列歸并排序后的有序序列。.void merge(int r ,int r1 ,int low,int m,int h) /*rlow.m及rm+1.h分別有序,歸并后置于r1中*/int i=low,j=m+1,k=low; /*i和j

19、是r的指示器*/ /*i的取值從l到m,j的取值從m+1到h;k是r1的指示器*/while (i=m & j=h)if (rim) /*前部分結(jié)束*/while (j=h) /*將后部分復(fù)制到r1*/r1k=rj; j+; k+;else /*后部分結(jié)束*/while (i2*len)merge(r,r1,p,p+len-1,p+2*len-1);p+=2*len; /p向后移動(dòng)2*l,準(zhǔn)備下一次合并if (n-p+1len) /一個(gè)長(zhǎng)度為len的部分與一個(gè)長(zhǎng)度小于len的部分合并merge(r,r1,p,p+len-1,n);else /只剩下一個(gè)長(zhǎng)度不大于len的部分,將其復(fù)制到r1fo

20、r (;p=n;p+) r1p=rp;.void mergesort(int r,int r1,int n)/*對(duì)r中數(shù)據(jù)元素進(jìn)行歸并,結(jié)果仍放在r中*/int len=1;while (lenn)mergepass(r,r1,n,len);len*=2; /*從r歸并到r1*/mergepass(r1,r,n,len);len*=2; /*從r1歸并到r*/void main()int a11=0,75,87,68,92,88,61,77,96,80,72;/*a0元素不計(jì)入元素個(gè)數(shù)*/int a110, n=10,i;mergesort(a,a1,n);for (i=1;i=n;i+)pr

21、intf(%6d,ai); . 歸并排序的非遞歸算法2：void merge(int r ,int r1 ,int low,int m,int h) /*rlow.m及rm+1.h分別有序,歸并后置于r1中*/int i=low,j=m+1,k=low; while (i=m & j=h)if (rim) /*前部分結(jié)束*/while (j=h) /*將后部分復(fù)制到r1*/r1k=rj; j+; k+;else /*后部分結(jié)束*/while (i=m) /*將前部分復(fù)制到r1*/r1k=ri; i+; k+;for (i=low; i=h; i+)ri=r1i;返回遞歸函數(shù).void sort

22、(int a ,int b ,int n) /自底向上排序/ 將數(shù)組a0,a1, an-1排序/ 利用數(shù)組b 過(guò)渡,b與a的長(zhǎng)度相等int i,len;len=1;while ( lenn )i=0;while ( i+2*len=n )merge(a,b,i,i+len-1,i+2*len-1);i=i+2*len; if ( i+lenn )merge(a,b,i,i+len-1,n-1);len=len*2;.7、堆排序利用完全二叉樹對(duì)數(shù)組排序： 1、將一個(gè)無(wú)序序列建成堆， 2、輸入出頂點(diǎn)元素后，調(diào)整并重建堆， 3、重復(fù)2直至全部元素都輸出完畢。.void sift(int p ,int

23、 i,int n)/調(diào)整數(shù)組p的第i元素,n為數(shù)組長(zhǎng)度 int j,t; t=pi; j=2*(i+1)-1; /左子樹 while(j=n) if ( (jn) & (pjpj+1) ) j+; /右子樹 if( t=0;i-) /初始建堆 sift(p,i,n-1); for(i=n-1;i=1;i-) /重建堆 t=p0; p0=pi; pi=t; sift(p,0,i-1); void main( ) int i, a10=75,87,68,92,88,61,77,96,80,72; sort(a,10); for(i=0;i10;i+) printf(%d,ai);.五、遞歸排序算法1、選擇排序的遞歸算法/對(duì)數(shù)組a中的元素