算法1

(暴力枚举) $O(n^2)$

暴力无脑算法，直接计数冒泡的个数
当然是会超时

时间复杂度

参考文献

java 代码

import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner s= new Scanner(System.in);
        int n=s.nextInt();
        while(n!=0){
        int[] nums = new int[n];
        for(int i=0;i<n;i++)
            {
                nums[i]=s.nextInt();
            }
        int num = count(nums);
        System.out.println(num);
         n = s.nextInt();
        }
    }
    public static int count(int q[]){
        //冒泡排序的次数
        int t=0;
        for(int i=0;i<q.length;i++){
            for(int j=q.length-1;j>i;j--){
                if(q[j]<q[j-1])
                {
                    int temp=q[j];
                    q[j]=q[j-1];
                    q[j-1]=temp;
                    t++;
                }
                else continue;
            }
        }
        return t;
    }
}

算法2

(归并) $O(n^2)$

会将时间复杂度下降到nlogn

时间复杂度

参考文献

java 代码

import java.util.Scanner;
public class Main{
    static long count;
    public static void main(String args[]){
        Scanner s= new Scanner(System.in);
        // while(s.hasNext()){
        //     count=0;
        //     int n=s.nextInt();
        //     if(n == 0) break;
        //     long nums[] = new long[n];
        //     for(int i=0;i<n;i++){
        //         nums[i]=s.nextLong();
        //     }
        //     meger(nums,0,n-1);
        //     System.out.println(count);
        // }
        int n=s.nextInt();
        while(n!=0){
            count=0;
            long[] nums = new long[n];
            for(int i=0;i<nums.length;i++)
              {
                nums[i]=s.nextLong();//java.util.NoSuchElementException
              }
            meger(nums,0,n-1);
            System.out.println(count);
            n = s.nextInt();
        }
        s.close();
    }
    public static void meger(long q[],int l,int r){
        //本来的时间复杂度是n*n，只能变成nlogn，归并就是一种方法
        //基线条件
        if(r-l<1) return ;
        int m = l+r>>1;
        meger(q,l,m);//左边逆序对的个数
        meger(q,m+1,r);//右边逆序对的个数
        int i =l;
        int j =m+1;
       int t=0;
        long temp[]=new long[r-l+1];
        while(i<=m&&j<=r)
        {
            if(q[i]>q[j]) {
                count+=m-i+1;//前提是拍好序的数列
                temp[t++]=q[j++];
            }
           else temp[t++]=q[i++];
        }
        while(i<=m) temp[t++]=q[i++];
        while(j<=r) temp[t++]=q[j++];
        for(int g=0;g<r-l+1;g++){
            q[g+l]=temp[g];
        }
        return;
    }
}