我正在计算交换的泡沫排序数量，但时间超过

Question

我正在解决一个问题它是要计算冒泡排序中的交换次数。

解决需要的时间1000毫秒

n：元素数datai =元素

输入

2 < n<=2000000

1<=datai<=n 

样本输入

5
3 3 2 2 1

样本输出

8

这是我的代码：

#include <iostream>

using namespace std;

int s[2000005];

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    int ans=0;
    int flagg=0;
    int c;
    for(int k=0;k<n-1;k++){
        flagg=0;

        for(int i=0;i<n-1-k;i++){
            if(s[i]>s[i+1]){
                c=s[i];
                s[i]=s[i+1];
                s[i+1]=c;

                ans++;
                flagg=1;
            }

        }    
                if(flagg!=1)
            break;
    }

    cout<<ans<<endl;

    return 0;
}

但是我总是会超过时间限制

有人知道我怎么能更快？

Answer 1

您的内部循环应如下所示：

for(int k=0;k<n-1;k++){
    for(int i=k+1;i<n;i++){
        if(s[i]>s[k]){
            std::swap( s[i], s[k] );
            ans++;
        }
    }    
}

有关详细信息，请检查How to find number of expected swaps in bubble sort in better than O(n^2) time