什么做网站,该网站的域名为,营销型网站建设价格贵吗,多城市网站开发排序系列之(1)归并排序及C语言实现有很多算法在结构上是递归的#xff1a;为了解决一个给定的问题#xff0c;算法需要一次或多次递归的调用其本身来解决相关的问题。这些算法通常采用分治策略#xff1a;将原问题划分成n个规模较小而结构与原问题相似的子问题#xff1b;递…排序系列之(1)归并排序及C语言实现有很多算法在结构上是递归的为了解决一个给定的问题算法需要一次或多次递归的调用其本身来解决相关的问题。这些算法通常采用分治策略将原问题划分成n个规模较小而结构与原问题相似的子问题递归的解决这些子问题然后将结果合并就能得到原问题的解。分治模式在递归时一般都有三个步骤分解将原问题分解成一系类子问题解决递归的解各子问题。若子问题足够小则直接求解。合并将子问题的结果合并成原问题的解。归并排序在算法上完全依照了上述模式操作如下。分解将n个元素分解成n/2个元素的子序列解决用合并排序法对两个子序列递归地排序合并将子问题的结果合并原问题的解。以下是源代码实现view plaincopy to clipboardprint?void mergeSort(int a[],int left,int right){int i;// 保证至少有两个元素if(left right){i (leftright)/2;mergeSort(a,left,i);mergeSort(a,i1,right);merge(a,left,right);}}void merge(int a[],int left,int right){int begin1 left;int mid (leftright)/2 ;int begin2 mid1;int k0;int newArrayLen right-left1;int *b (int*)malloc(newArrayLen*sizeof(int));while(begin1mid begin2right){if(a[begin1]a[begin2])b[k] a[begin1];elseb[k] a[begin2];}while(begin1mid)b[k] a[begin1];while(begin2right)b[k] a[begin2];copyArray(b,a,newArrayLen,left);free(b);}/*** 复制数组* source:源数组* dest:目标数组* len:源数组长度* first:目标数组起始位置**/void copyArray(int source[], int dest[],int len,int first){int i;int jfirst;for(i0;i{dest[j] source[i];j;}}void mergeSortTest(){int a[] {5, 18, 151, 138, 160, 63, 174, 169, 79, 200};int len sizeof(a)/sizeof(int);showArray(a,len);mergeSort(a,0,len-1);showArray(a,len);}
