归并排序+逆序对个数
程序员文章站
2022-05-10 11:51:29
...
void merge_sort(int* A,int x,int y,int* T)
{
if(y - x <= 1) return;int cnt = 0;
int m = x + (y - x) / 2; //划分
merge_sort(A,x,m,T);merge_sort(A,m,y,T);//分别对子问题求解
int p = x, q = m, i = x,cnt = 0;
while(q < m || p < y)
{
if(q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++];
//左半部分较小时 或 右半部分已全部加入时,从左半数组复制到临时空间
else
{
T[i++] = A[q++];//否则从右半数组复制到临时空间
cnt += m - p; //因为先放入的p个元素都比右边这个元素小,所以此时对右边每个元素,左边比它大的元素有m-p个
}
}
for(i = x;i < y;i++)
A[i] = T[i];//从临时空间复制回A数组
}
下一篇: 求逆序对(归并排序)