考研要求掌握C语言（归并排序）

归并排序考啥？

在考研中归并排序只出在选择题，理解原理很重要

且在考研中考两两归并，还是比较简单的

归并排序原理

就是每次分一半，直到每一半只含有一个或不能再分时，一半一半的进行排序，最终合并两个有序的数组

代码实战

//核心代码
void merge(int nums[],int low,int mid,int high)
{//合并数组两个有序的数组static int tmp[N];//创建一个和元数组一样大的数组进行合并，//加上static关键字是为了在递归过程中只创建一次for(int t=low;t<=high;t++){tmp[t]=nums[t];//把当前low到high数据全部拷贝在临时数组中}//这里都是下标，所以可以等于int i,j,k;//注意k是合并数组的起始下标即low，千万别错for(k=low,i=low,j=mid+1;i<=mid && j<=high; k++){if(tmp[i]<=tmp[j]){nums[k]=tmp[i++];}else{nums[k]=tmp[j++];}}//判断单独多余的那个，因为不知道哪一半数据是比另一半多的//所以要都判断while(i<=mid){nums[k++]=tmp[i++];}while(j<=high){nums[k++]=tmp[j++];}}void merge_sort(int nums[],int low,int high)
{if(low < high){int mid = (low+high)/2;merge_sort(nums,low,mid);merge_sort(nums,mid+1,high);merge(nums,low,mid,high);}
}

 可运行代码

#include<stdio.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
#define N 10
void swap(int &a,int &b)
{int tmp=a;a=b;b=tmp;
}void rangnums(int nums[],int len)
{srand(time(NULL));//初始化数组printf("初始化数组:");for(int i=0;i<len;i++){nums[i]=rand()%100+1;printf("%d ",nums[i]);}puts("");
}void print(int a[],int len)
{for(int i=0;i<len;i++){printf("%d ",a[i]);}puts("");
}void merge(int nums[],int low,int mid,int high)
{//合并数组两个有序的数组static int tmp[N];//创建一个和元数组一样大的数组进行合并，//加上static关键字是为了在递归过程中只创建一次for(int t=low;t<=high;t++){tmp[t]=nums[t];//把当前low到high数据全部拷贝在临时数组中}//这里都是下标，所以可以等于int i,j,k;//注意k是合并数组的起始下标即low，千万别错for(k=low,i=low,j=mid+1;i<=mid && j<=high; k++){if(tmp[i]<=tmp[j]){nums[k]=tmp[i++];}else{nums[k]=tmp[j++];}}//判断单独多余的那个，因为不知道哪一半数据是比另一半多的//所以要都判断while(i<=mid){nums[k++]=tmp[i++];}while(j<=high){nums[k++]=tmp[j++];}}void merge_sort(int nums[],int low,int high)
{if(low < high){int mid = (low+high)/2;merge_sort(nums,low,mid);merge_sort(nums,mid+1,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)