您的当前位置：首页树状数组------冒泡排序的交换次数

树状数组------冒泡排序的交换次数

来源：榕意旅游网

题意：
给定一个1~n的排列a0, a1, a2, ..., an-1, 求对这个数列进行冒泡排序所需要的交换次序(冒泡排序是每次找到满足ai > ai+1 的i，并交换ai 和 ai+1,直到这样的i不存在为止的算法)。

input：

n = 4, a = {3, 1, 4, 2}

output:

所求的交换次序等价于满足i < j, ai > aj 的(i, j)数对的个数（这种数对的个数叫做逆序数）。

建立一个1~n的BIT，按照 j = 0,1,2,3,4,...,n-1的i的个数顺序进行如下操作：

1. 把 j - (BIT查询得到的前aj项的和)加到答案中

2.把BIT中aj为止上的值加上1

我的理解：

j - 前面比自己小于等于的数

然后把当前数加到树状数组里

因为当前的数已经属于下个数之前的数了

这样，树状数组就能求出前面小于等于a[j]的数的个数了

即（1,4）（3,4）（1,2）

<strong><span style="font-size:14px;">#include<iostream>
using namespace std;
#define MAX_N 100
int bit[MAX_N + 1], n;
int a[MAX_N];
int sum(int i){
    int s = 0;
    while(i > 0){
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, int x){
    while(i <= n){
        bit[i] += x;
        i += i & -i;
    }
}
void solve()
{
    long long ans = 0;
    for(int j = 0; j < n; ++j){
        ans += j - sum(a[j]);
        add(a[j], 1);
    }
    printf("%lld\n", ans);
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d", &a[i]);
    }
    solve();
    return 0;
}</span></strong>

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

树状数组------冒泡排序的交换次数

题意： 给定一个1~n的排列a0, a1, a2, ..., an-1, 求对这个数列进行冒泡排序所需要的交换次序(冒泡排序是每次找到满足ai > ai+1 的i， 并交换ai 和 ai+1,直到这样的i不存在为止的算法)。

题意：
给定一个1~n的排列a0, a1, a2, ..., an-1, 求对这个数列进行冒泡排序所需要的交换次序(冒泡排序是每次找到满足ai > ai+1 的i，并交换ai 和 ai+1,直到这样的i不存在为止的算法)。