编程论坛 → 数据结构与算法

帮忙设计算法

qiezifxj 发布于 2010-04-12 20:59， 531 次点击

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

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

5 回复

qiezifxj2010-04-13 11:21

没人回啊！！！

mywaylgh2010-04-14 11:24

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

linjx01232010-04-14 16:31

这个应该就是冒泡排序吧
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;
        }
    }
}

asdjc2010-04-16 07:16

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

qq88011032010-04-17 22:26

楼住指明要用二分法吗