编辑代码

#include <stdio.h>
#include <stdlib.h>

int merge(int *a,int *temp,int first,int mid,int last){
    int n = mid,m = last;
    int k = 0;
    int i = first,j = mid+1;
    int count = 0;

    while(i <= n && j <= m){ 
        if(a[i] <= a[j]){ 
            temp[k++] = a[i++]; 
        }else{
            temp[k++] = a[j++]; 
            count +=(mid-i+1);
        }

    }

    while(i <= n){
        temp[k++] = a[i++];
    }

    while(j <= m){
        temp[k++] = a[j++];
    }

    for(i = 0; i < k; i++){
        a[first+i] = temp[i];
    }
    return count;
}



int mergeSort(int *a,int *temp,int first,int last){
    int count = 0;
    if(first < last){ 
        int mid = (first+last)/2; 
        count = count + mergeSort(a,temp,first,mid); 
        count = count + mergeSort(a,temp,mid+1,last); 
        count = count + merge(a,temp,first,mid,last); 
    }
    return count;
}



int sort(int *a,int n){
    int *p = malloc(n); 
    if(p == NULL){
        return -1;
    }else{
        free(p);
        printf("逆序数的个数为：%d\n",mergeSort(a,p,0,n-1));
        p = NULL;
        return 1;
    }
}

int main(){
    int a[]={9,12,8,7,3};
    int len=sizeof(a)/sizeof(int);
    sort(a,len); 
    for(int i = 0; i < len; i++){
        printf("%d ",a[i]);
    }
    printf("\n");
    
    return 0;

}