【题解】泡泡排序

题意

给你一个长度为的排列，让你把这个数组变成从小到大排列，你可以每次选择一个数字将其和前面一个数字进行交换，其条件是必须前一个比现在的小，该操作会一直进行下去直到前一个比当前数大。问最少选择多少个数字。

题解

我们可以贪心的去想，对于当前这个数来说若后面的数比他大的话，后面的数一定会向前移动的，那就等于后面这个数肯定是有被选择的，那我们可以交换当前这个数和后面数的位置以及答案加一。然后由于是当前数和后面的数交换，实际上后面的数换到前面来前面的数据我们以及处理过了，就可以管用管了，继续去找下一个数就可以了。这样遍历下来只要发现后面的数比当前数大就交换，并答案加一，遍历完就是最终要选的数的个数了。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&a[i]);
        }
        int ans=0;
        for(int i=0; i<n-1; i++)
        {
            if(a[i]<a[i+1])
            {
                swap(a[i], a[i+1]);
                ans++;
            }
        }
        printf("%d\n",ans);
    }
}