时间复杂度O（nlog2n）

归并排序：

void Merge(int l,int mid,int r)

{

    int i=l,j=mid+1,k=0;

    while(i<=mid && j<=r)

    {

        if(a[i]>a[j])

        {

            t[k++]=a[j++];

            cnt+=mid-i+1;

        }

        else

        {

            t[k++]=a[i++];

        }

    }

    while(i<=mid) t[k++]=a[i++];

    while(j<=r) t[k++]=a[j++];

    //将归并完成的结果复制到原数组中

    for(i=0; i<k; i++)

    {

        a[l+i]=t[i];

    }

}

      一趟冒泡排序需要进行的是n-1,n-2,……,2,1,0的和次比较。即n*(n-1)/2次。总的时间复杂度为O(n^2).

冒泡排序：

 

for(i=0; i
     
      a[j+1])                 {                     int tem=a[j];                        a[j]=a[j+1];                     a[j+1]=tem;                     cnt++;                     flag=true;                 }            }            if(!flag)  //本轮没交换。则成功            {                 break;            }        }