数据结构-归并排序 （C++代码）

解题思路:

注意事项:

参考代码:

#include<cstdio>

#include<malloc.h>

void Merge(int arr[],int tempArr[],int begin,int end){

if(begin>=end)return;

int mid=(begin+end)/2;

int s1=begin;

int s2=mid+1;

int pos=begin;

int num=end-begin+1;

while(s1<=mid&&s2<=end){

if(arr[s1]>arr[s2])

tempArr[pos++]=arr[s2++];

else

tempArr[pos++]=arr[s1++];

}

while(s1<=mid)

tempArr[pos++]=arr[s1++];

while(s2<=end)

tempArr[pos++]=arr[s2++];

pos--;

for(int i=0;i<num;i++,pos--){

arr[pos]=tempArr[pos];

}

}

void assist(int arr[],int temp[],int begin,int end){

if(begin>end)return;

if(begin!=end){

int mid=(begin+end)/2;

assist(arr,temp,begin,mid);

assist(arr,temp,mid+1,end);

}else

return;

Merge(arr,temp,begin,end);

}

void merge_sort(int arr[],int size){

int* temp=(int*)malloc(size*sizeof(int));

assist(arr,temp,0,size-1);

}

int main(){

int size;

scanf("%d",&size);

int* arr=(int*)malloc(size*sizeof(int));

for(int i=0;i<size;i++)

scanf("%d",&arr[i]);

merge_sort(arr,size);

for(int i=0;i<size;i++)

printf("%d ",arr[i]);

return 0;

}