请问怎么做到时间复杂度为O(nlogn)呢？谢谢解答。

Kitty喜欢小鱼干

Kitty喜欢小鱼干

#include <stdio.h>

//时间复杂度为O(n^2)
int NiXuNUM(int a[], int n){
    int i, j, count=0;

    for( i=0; i<n-1; i++ ){
        for( j=i+1; j<n; j++ ){
            if( a[i]>a[j] )
                count++;
        }
    }
    printf("%d", count);
    return count;
}

int main(){
    int a[5] = {5, 4, 3, 2, 1};
    NiXuNUM(a, 5);
    return 0;
}

claws0n

归并排列，不要排列就可以计算逆序对。今天没电脑哈

Kitty喜欢小鱼干

claws0n 发表于 2018-10-28 15:17
归并排列，不要排列就可以计算逆序对。今天没电脑哈

谢谢版主，我试试！！！