#include <time.h>
void mergeSortBU(int arr[],int n);
void merge(int *arr,int l,int mid,int r);
int minab(int a,int b);
int main()
{
int n=10;
int i;
int a[10]={1,3,2,5,4,6,7,8,9,10};
/*srand(time(NULL));
for(i=0;i<n;i++)
{
a[i]=rand()%(99)+1;
}*/
for(i=0;i<n;i++)
{
printf("%3d",a[i]);
}
mergeSortBU(a,n);
for(i=0;i<n;i++)
{
printf("%3d",a[i]);
}
return 0;
}
void mergeSortBU(int arr[],int n)
{
int size,i;
for(size=1;size<=n;size+=size)
{
for(i=0;i<n;i+=size+size)
{ //这里改为i+size <n确保了后一段的存在,也保证了下标值不会越界
merge(arr,i,i+size-1,minab(i+size+size-1,n-1));
} //这里与n-1取最小值可以保证我们最后一个下标不会越界
}
}
int minab(int a,int b)
{
if(a>b)
return b;
else
return a;
}
//将arr[l,mid] 和 arr[mid+1,r]两部分进行归并
void merge(int *arr,int l,int mid,int r)
{
int aux[r-l+1];
int i=l;
for(i=l;i<=r;i++)
{
aux[i-l]=arr[i];//aux是从0开始,而arr是从l开始,所以会有l个偏移
}
int j=mid+1;
int k;
for(k=l;k<=r;k++)
{
if(i>mid)
{
arr[k]=aux[j-l];
j++;
}
else if(j>r)
{
arr[k]=aux[i-l];
i++;
}
else if(aux[i-l]>aux[j-l])
{
arr[k]=aux[j-l];
j++;
}
else
{
arr[k]=aux[i-l];
i++;
}
}
}