冒泡排序（优化版）的比较次数和交换数字次数逆序数+树状数组

思路：

要求冒泡排序优化以后的趟数和交换次数
交换次数等于逆序数
因为冒泡排序是临对换排序，临对换一次减少一个逆序对
冒泡的趟数：
求出每个数a[i]的前面比它大的数的个数记为b[i]
答案是max{b[]}+1
最后一趟没有swap
总共冒泡max{b[]}+1这么多趟
因为对于每个数，每一趟都把它前面比他大的一个数移到了它的后面
max{b[]}趟以后每个数前面都没有比它大的了，。。，，。
整体有序。。，。

（思路来自neko13）

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
       #define N 100010 using namespace std; int c[N], maxn; inline int Lowbit(int x){return x&(-x);} int sum(int i)//单点更新i点改为x { int ans = 0; while(i<=maxn) { ans += c[i]; i+=Lowbit(i); } return ans; } void change(int x, int value){//[1,x]增量为value for(int i = x; i >= 1; i -= Lowbit(i)) c[i] += value; } int a[N]; set
       
        myset; set
        
         ::iterator p; map
         
          mymap; int main(){ int n, i; while(~scanf(%d,&n)){ myset.clear(); mymap.clear(); maxn = n+1; //离散 for(i = 0; i < n; i++)scanf(%d,&a[i]), myset.insert(a[i]); int top = 1; for(p = myset.begin(); p!=myset.end(); p++) mymap.insert(pair
          
           (*p, top++)); for(i = 0; i < n; i++) { a[i] = mymap.find(a[i])->second; c[i] = 0; } // int maxx = 0, he = 0; for(i = 0; i < n; i++) { int ni = sum(a[i]); change(a[i], 1); maxx = max(ni, maxx); he += ni; } int ans2 = 0; maxx++; while(maxx--)ans2 += --n; printf(%d %d , ans2, he); //交换次数是 ： 逆序数 (交换次数等于逆序数因为冒泡排序是临对换排序， 临对换一次减少一个逆序对) //排序的趟数是 max(每个数字的逆序) +1(最后一趟不交换) } return 0; } /* 5 5 1 2 3 4 */

冒泡排序（优化版）的比较次数和交换数字次数 逆序数+树状数组