归并排序的原理是不断地将两个有序的序列合并为一个有序列,设有n个元素,那么第一步是长度为1的序列进行合并,第二步是长度为2的序列进行合并,第3步是长度为4的序列进行合并,以此类推。算法的时间复杂度是O(nlogn)。下面是我的代码:
#include <stdio.h> #include <conio.h> //函数原型 void sort_parallel(int target[],int start1,int start2,int num,int n); int main() { //定义变量 int a[]={1,5,3,6,7,4,2}; int n=7;//需要排序的元素的个数 int num=1;//归并组的元素间隔从1开始 //排序 while(num<n) { for(int i=0;i<n/num && 2*i*num<n;i++) { int temp_start=2*i*num; sort_parallel(a,temp_start,temp_start+num,num,n); } num*=2; } //输出排序后的元素 for(int m=0;m<n;m++) printf("%d",a[m]); getch(); } //为两个有序序列进行排序 //这里的重点是传入哪些参数最佳 void sort_parallel(int target[],int start1,int start2,int num,int n) { int flag=0; int temp_array[10]={0}; int i=0,j=0; while(i<num && j<num && start1+i<n && start2+j<n ) { if(target[start1+i]<target[start2+j]) { temp_array[flag++]=target[start1+i]; i++; } elseif(target[start1+i]==target[start2+j]) { temp_array[flag++]=target[start1+i]; i++;j++; } else { temp_array[flag++]=target[start2+j]; j++; } } while(i<num && start1+i<n) temp_array[flag++]=target[start1+i++]; //这里又是粗心错误,忘记把i自加了 while(j<num && start2+j<n) temp_array[flag++]=target[start2+j++]; //把有序序列覆盖到原数组 for(i=start1,j=0;i<n && i<start1+2*num;i++,j++) target[i]=temp_array[j]; }
总结:本来前天就把这段代码写好,但运行的时候老是出错,就先放置了。今天继续来找错的时候突然发现忘了把其中一个地方的i,j自加了。我老是犯这样的低级错误。虽然一直在努力避免,但还是偶尔会粗心弄错。另外,我不止一次的体会到,当程序出现自己暂时无法调出的bug时,最好先把错误放一放,也许过一会就能很快的改正错误。
以上代码小弟已经尽我的最大努力进行了优化,但我水平还很低,如果您觉得有可以改进的地方,欢迎您指出来,或者有错的地方也欢迎指出,非常感谢。