//只是实现了归并排序,但是没用来解决这个题
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define int long long
using namespace std;
//合并 + 排序
void merge(int arr[],int tempArr[],int left,int mid,int right)
{
//标记左半区第一个未排序的元素
int lp=left;
//标记右半区第一个未排序的元素
int rp=mid+1;//mid属于左半区,mid+1是右半区的开始
//临时数组元素的下标
int p=left;
//合并
while(lp<=mid&&rp<=right)//左半区和右半区都还有剩余的元素
{
if(arr[lp]<arr[rp]) //左半区第一个剩余元素更小
tempArr[p++]=arr[lp++];
else//右半区第一个剩余元素更小
tempArr[p++]=arr[rp++];
}
//合并左半区剩余的元素
while(lp<=mid)
tempArr[p++]=arr[lp++];
//合并右半区剩余的元素
while(rp<=right)
tempArr[p++]=arr[rp++];
//把临时素组中合并后的元素复制回原来的元素
while(left<=right)
{
arr[left]=tempArr[left];
left++;
}
}
//2.归并排序--划分合并
void msort(int arr[],int tempArr[],int left,int right)
{
//如果只有一个元素,不需要划分,只需要归并
if(left<right) //只有存在多个元素时,才需要划分
{
int mid=left+right>>1;//找中间点
msort(arr,tempArr,left,mid);//递归划分左半边区域
msort(arr,tempArr,mid+1,right); //递归划分右半边区域
merge(arr,tempArr,left,mid,right);//合并已经排序的两个区域
}
}
//1.归并排序入口
void mergesort(int arr[],int n)
{
//分配一个辅助数组
int* tempArr=(int*)malloc(n*sizeof(int));
if(tempArr) // 表示辅助数组分配成功,也就是该数组不为空,此时进行排序
{
msort(arr,tempArr,0,n-1);
free(tempArr);//释放辅助数组
}
else
{
cout<<"error:分配失败";
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int arr[]={9,5,2,7,12,4,3,1,11};
int n=9;
for(int i=0;i<n;i++)
cout<<arr[i]<<' ';
mergesort(arr,n);//排序入口
cout<<endl;
for(int i=0;i<n;i++)
cout<<arr[i]<<' ';
return 0;
}