题目大意：输入n个互不相同的正整数，每次只能交换两个相邻的数字，为了从小到大排序，至少要交换几次？

我自己只能找到O(n^2)的算法，但是会超时。
希望有高手设计出O(n)或者O(n*logn)的算法

没人回啊！！！

这么多排序算法，都是已经很成熟了的，何必自找麻烦呢：）

这个应该就是冒泡排序吧
for(int i=0;i<n-1;i++){
    for(int j=1;j<n-i;j++){
        if(a[i]>a[j]){
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }
    }
}

排序方式有很多，冒泡，shell，堆，快速等等。但平均最快的是（nlogn）。
楼主你有o（n/2）的算法？？？
拿来看看！！！

楼住指明要用二分法吗