首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

算法导论——归并排序兑现

2012-09-19 
算法导论——归并排序实现最近学习《算法导论》,整理一下每章的笔记,并且会将书上的伪代码用C语言实现。分治模

算法导论——归并排序实现
  最近学习《算法导论》,整理一下每章的笔记,并且会将书上的伪代码用C语言实现。   分治模式的一般步骤:  (1)分解(Divide):将原问题分解成一系列自问题
  (2)解决(Conquer):递归的解各子问题。若问题足够小,则直接求解(递归结束的条件)
  (3)合并(Combine):将子问题的结果合并成原问题的解  对于归并排序的递归实现,则完全依照了上述模式:
  (1)分解:将N个元素分成个含N/2个元素的子序列
  (2)解决:用合并排序法对两个子序列递归的排序
  (3)合并:合并两个已排序的子序列以得到排序结果
代码如下(ps:递归实现了归并排序,同时增加了二分查找的代码):

#include <stdio.h>#define MAX 65535void Merge(int *A,int p,int q,int r);void MergeSort(int *A,int p,int r);void PrintArray(int *A,int size);int BinarySearch(int *A,int key,int begin,int end);int main(void){int i,size,key,location;int A[1000]={0};printf("请输入排序数组的大小: ");scanf("%d",&size);for(i = 0; i < size; i++){scanf("%d",&A[i]);}//归并排序并打印数组MergeSort(A,0,size-1);printf("排序好的数组元素: ");PrintArray(A,size);printf("请输入查找元素: ");scanf("%d",&key);location=BinarySearch(A,key,0,size-1);if( location == -1 ){printf("元素没有找到\n");}else{printf("元素的位置在%d\n",location);}return 0;}void Merge(int *A,int p,int q,int r){int i,j,k;//定义数组A[p..q]和A[q+1..r]的长度int n1 = (q - p + 1);int n2 = (r - q);int Larray[n1],Rarray[n2];for(i = 0; i < n1; i++){Larray[i] = *(A + p + i);}for(j = 0; j < n2; j++){Rarray[j] = *(A + q +1 + j);}//哨兵位置Larray[n1] = MAX;Rarray[n2] = MAX;for(i = 0,j = 0,k = p; k <= r; k++){if(Larray[i] <= Rarray[j]){*(A + k) = Larray[i++];}else{*(A + k) = Rarray[j++];}}}/** * Description:归并排序主流程函数 */void MergeSort(int *A,int p,int r){int q;if(p < r){q = (int)( p + r ) / 2;MergeSort(A,p,q);MergeSort(A,q+1,r);Merge(A,p,q,r);}}/** * Description:打印数组 */void PrintArray(int *A,int size){int i;for(i = 0; i < size; i++){printf("%d ",*(A+i));}printf("\n");}/** * Description:二分查找 */int BinarySearch(int *A,int key,int begin,int end){while( begin <= end ){int mid = ( begin + end ) / 2; if(key > *(A + mid)){begin = mid + 1 ;}else if(key < *(A + mid)){end = mid - 1;}else{return mid+1;}}return -1;}





热点排行