重庆做网站泉州公司,辽阳企业网站建设团队,第一模板网站上的模板怎么下载,做网站准备的资料归并排序考啥#xff1f;
在考研中归并排序只出在选择题#xff0c;理解原理很重要
且在考研中考两两归并#xff0c;还是比较简单的
归并排序原理
就是每次分一半#xff0c;直到每一半只含有一个或不能再分时#xff0c;一半一半的进行排序#xff0c;最终合并两个…归并排序考啥
在考研中归并排序只出在选择题理解原理很重要
且在考研中考两两归并还是比较简单的
归并排序原理
就是每次分一半直到每一半只含有一个或不能再分时一半一半的进行排序最终合并两个有序的数组 代码实战
//核心代码
void merge(int nums[],int low,int mid,int high)
{//合并数组两个有序的数组static int tmp[N];//创建一个和元数组一样大的数组进行合并//加上static关键字是为了在递归过程中只创建一次for(int tlow;thigh;t){tmp[t]nums[t];//把当前low到high数据全部拷贝在临时数组中}//这里都是下标所以可以等于int i,j,k;//注意k是合并数组的起始下标即low千万别错for(klow,ilow,jmid1;imid jhigh; k){if(tmp[i]tmp[j]){nums[k]tmp[i];}else{nums[k]tmp[j];}}//判断单独多余的那个因为不知道哪一半数据是比另一半多的//所以要都判断while(imid){nums[k]tmp[i];}while(jhigh){nums[k]tmp[j];}}void merge_sort(int nums[],int low,int high)
{if(low high){int mid (lowhigh)/2;merge_sort(nums,low,mid);merge_sort(nums,mid1,high);merge(nums,low,mid,high);}
} 可运行代码
#includestdio.h
#includestring.h
#includetime.h
#includestdlib.h
#define N 10
void swap(int a,int b)
{int tmpa;ab;btmp;
}void rangnums(int nums[],int len)
{srand(time(NULL));//初始化数组printf(初始化数组:);for(int i0;ilen;i){nums[i]rand()%1001;printf(%d ,nums[i]);}puts();
}void print(int a[],int len)
{for(int i0;ilen;i){printf(%d ,a[i]);}puts();
}void merge(int nums[],int low,int mid,int high)
{//合并数组两个有序的数组static int tmp[N];//创建一个和元数组一样大的数组进行合并//加上static关键字是为了在递归过程中只创建一次for(int tlow;thigh;t){tmp[t]nums[t];//把当前low到high数据全部拷贝在临时数组中}//这里都是下标所以可以等于int i,j,k;//注意k是合并数组的起始下标即low千万别错for(klow,ilow,jmid1;imid jhigh; k){if(tmp[i]tmp[j]){nums[k]tmp[i];}else{nums[k]tmp[j];}}//判断单独多余的那个因为不知道哪一半数据是比另一半多的//所以要都判断while(imid){nums[k]tmp[i];}while(jhigh){nums[k]tmp[j];}}void merge_sort(int nums[],int low,int high)
{if(low high){int mid (lowhigh)/2;merge_sort(nums,low,mid);merge_sort(nums,mid1,high);merge(nums,low,mid,high);}
}int main()
{int a[N]{92 ,79 ,49, 59, 86 ,38, 94, 64, 92, 3};// rangnums(a,10);merge_sort(a,0,9);print(a,10);} 时间复杂度
O(nlog2n)
空间复杂度
o(n)
