|
本章通過介紹插入排序和歸并排序兩種常見的排序算法來說明算法的過程及算法分析，在介紹歸并排序算法過程中引入了分治（divide-and-conquer）算法策略,。 1,、插入排序 輸入：n個(gè)數(shù)（a1,a2,a3,...,an） 輸出：輸入序列的一個(gè)排列（a1',a2',a3',...an'）使得（a1'≤a2'≤a3'≤...≤an'）。 插入排序的基本思想是：將第i個(gè)元素插入到前面i-1個(gè)已經(jīng)有序的元素中,。具體實(shí)現(xiàn)是從第2個(gè)元素開始（因?yàn)?個(gè)元素是有序的）,，將第2個(gè)元素插入到前面的1個(gè)元素中，構(gòu)成兩個(gè)有序的序列,，然后從第3個(gè)元素開始,，循環(huán)操作，直到把第n元素插入到前面n-1個(gè)元素中,，最終使得n個(gè)元素是有序的,。該算法設(shè)計(jì)的方法是增量方法。書中給出了插入排序的為代碼,，并采用循環(huán)不變式證明算法的正確性,。我采用C語言實(shí)插入排序,，完整程序如下：  1 void insert_sort(int *datas,int length) 2 { 3 int i,j; 4 int key,tmp; 5 //判斷參數(shù)是否合法 6 if(NULL == datas || 0==length) 7 { 8 printf("Check datas or length.\n"); 9 exit(1); 10 } 11 //數(shù)組下標(biāo)是從0開始的，從第二個(gè)元素（對(duì)應(yīng)下標(biāo)1）開始向前插入 12 for(j=1;j<length;j++) 13 { 14 key = datas[j]; //記錄當(dāng)前要插入的元素 15 i = j-1; //前面已經(jīng)有序的元素 16 //尋找待插入元素的位置,，從小到到排序,，如果是從大到小改為datas[i]<key 17 while(i>=0 && datas[i] > key) 18 { 19 /×tmp = datas[i+1]; 20 datas[i+1] = datas[i]; 21 datas[i] = tmp;×/ 這個(gè)過程不需要進(jìn)行交換，因?yàn)橐迦氲闹当４嬖趉ey中,，沒有被覆蓋掉,，在此感謝”兩生花“指出問題所在 插入排序算法的分析 算法分析是對(duì)一個(gè)算法所需的資源進(jìn)行預(yù)測，資源是指希望測度的計(jì)算時(shí)間,。插入排序過程的時(shí)間與輸入相關(guān)的。插入排序的最好情況是輸入數(shù)組開始時(shí)候就是滿足要求的排好序的,，時(shí)間代價(jià)為θ(n),，最壞情況下，輸入數(shù)組是按逆序排序的,，時(shí)間代價(jià)為θ(n^2),。 2、歸并排序 歸并排序采用了算法設(shè)計(jì)中的分治法,，分治法的思想是將原問題分解成n個(gè)規(guī)模較小而結(jié)構(gòu)與原問題相似的小問題,，遞歸的解決這些子問題，然后再去合并其結(jié)果,，得到原問題的解,。分治模式在每一層遞歸上有三個(gè)步驟： 分解（divide）：將原問題分解成一系列子問題。 解決（conquer）：遞歸地解答各子問題,，若子問題足夠小,，則直接求解。 合并（combine）：將子問題的結(jié)果合并成原問題的解,。 歸并排序（merge sort）算法按照分治模式,，操作如下： 分解：將n個(gè)元素分解成各含n/2個(gè)元素的子序列 解決：用合并排序法對(duì)兩個(gè)序列遞歸地排序 合并：合并兩個(gè)已排序的子序列以得到排序結(jié)果 在對(duì)子序列排序時(shí)，長度為1時(shí)遞歸結(jié)束,，單個(gè)元素被視為已排序好的,。歸并排序的關(guān)鍵步驟在于合并步驟中的合并兩個(gè)已經(jīng)有序的子序列，引入了一個(gè)輔助過程,，merge(A,p,q,r),，將已經(jīng)有序的子數(shù)組A[p...q]和A[q+1...r]合并成為有序的A[p...r]。書中給出了采用哨兵實(shí)現(xiàn)merge的偽代碼,，課后習(xí)題要求不使用哨兵實(shí)現(xiàn)merge過程,。在這個(gè)兩種方法中都需要引入額外的輔助空間，用來存放即將合并的有序子數(shù)組,，總的空間大小為n?，F(xiàn)在用C語言完整實(shí)現(xiàn)這兩種方法,，程序如下： 1 //采用哨兵實(shí)現(xiàn)merge 2 #define MAXLIMIT 65535 3 void merge(int *datas,int p,int q,int r) 4 { 5 int n1 = q-p+1; //第一個(gè)有序子數(shù)組元素個(gè)數(shù) 6 int n2 = r-q; //第二個(gè)有序子數(shù)組元素個(gè)數(shù) 7 int *left = (int*)malloc(sizeof(int)*(n1+1)); 8 int *right = (int*)malloc(sizeof(int)*(n2+1)); 9 int i,j,k; 10 //將子數(shù)組復(fù)制到臨時(shí)輔助空間 11 for(i=0;i<n1;++i) 12 left[i] = datas[p+i]; 13 for(j=0;j<n2;++j) 14 right[j] = datas[q+j+1]; 15 //添加哨兵 16 left[n1] = MAXLIMIT; 17 right[n2] = MAXLIMIT; 18 //從第一個(gè)元素開始合并 19 i = 0; 20 j = 0; 21 //開始合并 22 for(k=p;k<=r;k++) 23 { 24 if(left[i] < right[j]) 25 { 26 datas[k] = left[i]; 27 i++; 28 } 29 else 30 { 31 datas[k] = right[j]; 32 j++; 33 } 34 } 35 free(left); 36 free(right); 37 } 不采用哨兵實(shí)現(xiàn)，需要考慮兩個(gè)子數(shù)組在合并的過程中哪一個(gè)先合并結(jié)束,，剩下的那個(gè)子數(shù)組剩下部分復(fù)制到數(shù)組中,，程序?qū)崿F(xiàn)如下： 1 int merge(int *datas,int p,int q,int r) 2 { 3 int n1 = q-p+1; 4 int n2 = r-q; 5 int *left = (int*)malloc(sizeof(int)*(n1+1)); 6 int *right = (int*)malloc(sizeof(int)*(n2+1)); 7 int i,j,k; 8 memcpy(left,datas+p,n1*sizeof(int)); 9 memcpy(right,datas+q+1,n2*sizeof(int)); 10 i = 0; 11 j = 0; 12 for(k=p;k<=r;++k) 13 { 14 if(i <n1 && j< n2) //歸并兩個(gè)子數(shù)組 15 { 16 if(left[i] < right[j]) 17 { 18 datas[k] = left[i]; 19 i++; 20 } 21 else 22 { 23 datas[k] = right[j]; 24 j++; 25 } 26 } 27 else 28 break; 29 } 30 //將剩下的合并到數(shù)組中 31 while(i != n1) 32 datas[k++] = left[i++]; 33 while(j != n2) 34 datas[k++] = right[j++]; 35 free(left); 36 free(right); 37 } merge過程的運(yùn)行時(shí)間是θ(n)，現(xiàn)將merge過程作為歸并排序中的一個(gè)子程序使用,，merge_sort(A,p,r),對(duì)數(shù)組A[p...r]進(jìn)行排序,，實(shí)例分析如下圖所示： C語言實(shí)現(xiàn)如下： 1 void merge_sort(int *datas,int p,int r) 2 { 3 int q; 4 if(p < r) 5 { 6 q = (p+r)/2; //分解，計(jì)算出子數(shù)組的中間位置 7 merge_sort(datas,p,q); //對(duì)第一個(gè)子數(shù)組排序; 8 merge_sort(datas,q+1,r); //對(duì)第二個(gè)子數(shù)組排序 9 merge(datas,p,q,r); //合并; 10 } 11 } 歸并排序算法分析： 算法中含有對(duì)其自身的遞歸調(diào)用,，其運(yùn)行時(shí)間可以用一個(gè)遞歸方程（或遞歸式）來表示,。歸并排序算法分析采用遞歸樹進(jìn)行，遞歸樹的層數(shù)為lgn+1,，每一層的時(shí)間代價(jià)是cn,，整棵樹的代價(jià)是cn(lgn+1)=cnlgn+cn，忽略低階和常量c,，得到結(jié)果為θ(nlg n),。 3、課后習(xí)題 有地道題目比較有意思,，認(rèn)真做了做,，題目如下： 方法1：要求運(yùn)行時(shí)間為θ（nlgn），對(duì)于集合S中任意一個(gè)整數(shù)a,，設(shè)b=x-a,，采用二分查找算法在S集合中查找b是否存在，如果b存在說明集合S中存在兩個(gè)整數(shù)其和等于x,。而二分查找算起的前提是集合S是有序的,，算法時(shí)間為θ（lgn），因此先需要采用一種時(shí)間最多為θ(nlgn)的算法對(duì)集合S進(jìn)行排序,?？梢圆捎脷w并排序算法，這樣總的運(yùn)行時(shí)間為θ（nlgn）,，滿足題目給定的條件,。 具體實(shí)現(xiàn)步驟： 1、采用歸并排序算法對(duì)集合S進(jìn)行排序 2,、對(duì)集合S中任意整數(shù)a,，b=x-a，采用二分查找算法b是否在集合S中,，若在則集合S中存在兩個(gè)整數(shù)其和等于x,，如果遍歷了S中所有的元素，沒能找到b,，即集合S中不存在兩個(gè)整數(shù)其和等于x,。 采用C語言實(shí)現(xiàn)如下：  View Code
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 //非遞歸二叉查找 6 int binary_search(int *datas,int length,int obj) 7 { 8 int low,mid,high; 9 low = 0; 10 high = length; 11 while(low < high) 12 { 13 mid = (low + high)/2; 14 if(datas[mid] == obj) 15 return mid; 16 else if(datas[mid] > obj) 17 high = mid; 18 else 19 low = mid+1; 20 } 21 return -1; 22 } 23 24 //遞歸形式二分查找 25 int binary_search_recursive(int *datas,int beg,int end,int obj) 26 { 27 int mid; 28 if(beg < end) 29 { 30 mid = (beg+end)/2; 31 if(datas[mid] == obj) 32 return mid; 33 if(datas[mid] > obj) 34 return binary_search_recursive(datas,beg,mid,obj); 35 else 36 return binary_search_recursive(datas,mid+1,end,obj); 37 38 } 39 return -1; 40 } 41 //合并子程序 42 int merge(int *datas,int p,int q,int r) 43 { 44 int n1 = q-p+1; 45 int n2 = r-q; 46 int *left = (int*)malloc(sizeof(int)*(n1+1)); 47 int *right = (int*)malloc(sizeof(int)*(n2+1)); 48 int i,j,k; 49 memcpy(left,datas+p,n1*sizeof(int)); 50 memcpy(right,datas+q+1,n2*sizeof(int)); 51 i = 0; 52 j = 0; 53 for(k=p;k<=r;++k) 54 { 55 if(i <n1 && j< n2) 56 { 57 if(left[i] < right[j]) 58 { 59 datas[k] = left[i]; 60 i++; 61 } 62 else 63 { 64 datas[k] = right[j]; 65 j++; 66 } 67 } 68 else 69 break; 70 } 71 while(i != n1) 72 datas[k++] = left[i++]; 73 while(j != n2) 74 datas[k++] = right[j++]; 75 free(left); 76 free(right); 77 } 78 //歸并排序 79 void merge_sort(int *datas,int beg,int end) 80 { 81 int pos; 82 if(beg < end) 83 { 84 pos = (beg+end)/2; 85 merge_sort(datas,beg,pos); 86 merge_sort(datas,pos+1,end); 87 merge(datas,beg,pos,end); 88 } 89 } 90 91 int main(int argc,char *argv[]) 92 { 93 int i,j,x,obj; 94 int datas[10] = {34,11,23,24,90,43,78,65,90,86}; 95 if(argc != 2) 96 { 97 printf("input error.\n"); 98 exit(0); 99 } 100 x = atoi(argv[1]); 101 merge_sort(datas,0,9); 102 for(i=0;i<10;i++) 103 { 104 obj = x - datas[i]; 105 j = binary_search_recursive(datas,0,10,obj); 106 //j = binary_search(datas,10,obj); 107 if( j != -1 && j!= i) //判斷是否查找成功 108 { 109 printf("there exit two datas (%d and %d) which their sum is %d.\n",datas[i],datas[j],x); 110 break; 111 } 112 } 113 if(i==10) 114 printf("there not exit two datas whose sum is %d.\n",x); 115 exit(0); 116 } 程序執(zhí)行結(jié)果如下：
方法2：網(wǎng)上課后習(xí)題答案上面給的一種方法,，具體思想如下： 1、對(duì)集合S進(jìn)行排序,，可以采用歸并排序算法 2,、對(duì)S中每一個(gè)元素a，將b=x-a構(gòu)造一個(gè)新的集合S',，并對(duì)S’進(jìn)行排序 3,、去除S和S'中重復(fù)的數(shù)據(jù) 4、將S和S'按照大小進(jìn)行歸并,，組成新的集合T,，若干T中有兩隊(duì)及以上兩個(gè)連續(xù)相等數(shù)據(jù)，說明集合S中存在兩個(gè)整數(shù)其和等于x,。 例如：S={7,10,5,4,2,5},，設(shè)x=11，執(zhí)行過程如下： 對(duì)S進(jìn)行排序,，S={2,4,5,5,7,10}。 S'={9,7,6,6,4,1},排序后S’={1,4,6,6,7,9},。 去除S和S'中重復(fù)的數(shù)據(jù)后S={2,4,5,7,10},，S'={1,4,6,7,9} 歸納S和S'組成新集合T={1,2,4,4,5,6,7,7,9,10}，可以看出集合T中存在兩對(duì)連續(xù)相等數(shù)據(jù)4和7,，二者存在集合S中,，滿足4+7=11。 |
|
|
