归并排序
思路:
1.确定分界元素mid=(left+right)/2
2.递归分解数组,两两组合组成两个有序数组
3.归并,合二为一
int temp[100010];
merge_sort(int num[],int l,int r){
if(l>=r) return;//说明数组只有一个元素或没有元素,无需继续排序
int mid=(l+r)/2;
merge_sort(num,l,mid);
merge_sort(num,mid+1,r);//递归分解数组
int i=l,j=mid+1,count=0;
while(i<=mid&&j<=r){
if(num[i]<num[j]) temp[count++]=num[i++];
else temp[count++]=num[j++];
//元素比较,将较小元素放置到数组前面
}
while(i<=mid) temp[count++]=num[i++];
while(j<=r) temp[count++]=num[j++];
//将剩余元素补到数组后面
for(i=l,j=0;i<=r;i++,j++) num[i]=temp[j];
//将排好序的元素放回原数组中,完成排序
}
逆序对的数量
//问题:为何k的位置不同会对结果产生影响呢?
#include<stdio.h>
int count=0;
int temp[100010];
void merge_sort(int num[],int l,int r){
if(l>=r) return;
int mid=(l+r)/2;
merge_sort(num,l,mid);
merge_sort(num,mid+1,r);
int i=l,j=mid+1;int k=0;//关键所在
printf("%d\n",k);
while(i<=mid&&j<=r){
if(num[i]<=num[j]) temp[k++]=num[i++];
else{
temp[k++]=num[j++];
count+=mid-i+1;
}
}
while(i<=mid) temp[k++]=num[i++];
while(j<=r) temp[k++]=num[j++];
for(i=l,j=0;i<=r;i++,j++) num[i]=temp[j];
}
int main()
{
int n;
int num[100010];
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&num[i]);
merge_sort(num,0,n-1);
printf("%d\n",count);
return 0;
}
/*
原理理解:
每一次递归拆开数组中的元素,直到只剩下一个元素,这时候函数回跑,因为每一次l都是不同的,也就是每一个坐标上元素的改变,也就是说,再回到最后一步时,数组的两部分已经完成排好序了,
在这个过程中我们的temp数组每一次都会被重置,元素进行覆盖,并且都是从0开始的,
那么如果我们将k置于全局变量,那么每一次函数递归k都会发生改变,那么temp数组也就是不会被元素重置,并且会把(l,mid)区间结果覆盖(mid+1,r),导致结果出现错误。
*/