归并排序 基本思想 一、递归
//归并 void merge(int *arr,int * tmp,int left,int mid,int right) { int begin1=left; int end1=mid; int begin2=mid+1; int end2=right; int idx=left; while(begin1<=end1&&begin2<=end2) { if(arr[begin1]<=arr[begin2]) tmp[idx++]=arr[begin1++]; else tmp[idx++]=arr[begin2++]; } while(begin1<=end1) tmp[idx++]=arr[begin1++]; while(begin2<=end2) tmp[idx++]=arr[begin2++]; } void _merge(int *arr,int *tmp,int left,int right) { if(left<right) { int mid=(left+right)>>1; _merge(arr,tmp,left,mid); _merge(arr,tmp,mid+1,right); merge(arr,tmp,left,mid,right); memcpy(arr+left,tmp+left,sizeof(arr[0])*(right-left+1)); } } void merge_sort(int *arr,int size) { if(arr==NULL||size<=0) return ; int *tmp=new int[size]; _merge(arr,tmp,0,size-1); delete[] tmp; }二、非递归
void merge_nor(int *arr,int size) { int *tmp=new int[size]; int left=0; int right=size-1; int gap=1; while(gap<size) { for(int idx=0;idx<size;idx+=gap*2) { left=idx; int mid=left+gap-1; right=mid+gap; if(mid>=size) mid=size-1; if(right>=size) right=size-1; merge(arr,tmp,left,mid,right); } memcpy(arr,tmp,size*sizeof(int)); gap<<=1; } delete[] tmp; }