内容：

主要写一下大体思路和一些注意问题

关键字：逆序对/归并排序

思路：虽然题目中的要求是让你做冒泡排序，但很明显O(n^2)的时间复杂度会TLE。

我们可以观察到，进行交换操作的前提是前面一个数比后面一个数大，那么问
总的交换次数相当于是在问这个数比后面的几个数大。
因此可以转换为求逆序对问题。
在此基础上，归并排序不但可以达到O(n log n) 的时间复杂度，还便于在合并过程中统计逆序对。

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;

long long ans=0;
long long a[500020],b[500020];
int n;

void merge(int l,int mid,int r){
    if(l==r) return ;
//    if(l+1==r){
//        if(a[l]>a[r]){
//            swap(a[l],a[r]);        
//            ans++;                  在这个过程中对于一对的数直接排序并统计
//        }                           其实这段也可以不写，因为下面交换的情况已经包含了这种情况
//            return ;
//    }
    merge(l,(l+mid)>>1,mid);        //这是一个递归进行归并排序的过程
    merge(mid+1,(mid+1+r)>>1,r);
    int i=l, j=mid+1;
    for(int k=l;k<=r;k++)
        if(j>r||(i<=mid&&a[i]<a[j])) b[k]=a[i++];   //注意：如果j>r说明右半区间已经没有数
        else b[k]=a[j++],ans+=mid-i+1;              //所以直接看左半区间就好，此时左半区间已经
        for(int k=l;k<=r;k++)                       //排好序，因此直接将左半区间的数放入b数组即可
        a[k]=b[k];
}

inline void work(){
    for(int i=1;i<=n;i++)
    cin>>a[i];
    merge(1,(1+n)>>1,n);
    cout<<ans<<"\n";
    ans=0;                      //ans每次执行完一次清零
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n,n)
    work();
    return 0;
}

题解过于粗糙，还望见谅