say_he_he
2015-04-24 13:08
采纳率: 100%
浏览 1.9k
已采纳

关于冒泡排序法的疑惑

冒泡排序法的代码

        int n=0;
        int temp = 0;
        for (int i = a.length - 1; i > 0; --i) {
            for (int j = 0; j < i; ++j) {
                if (a[j + 1] < a[j]) {
                    temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    n++;
                }
            }
        }

由于我是菜鸟,我写的是这样的

        int n = 0;
        int temp = 0;
        for (int i = a.length - 1; i > 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (a[i] < a[j]) {
                    temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    n++;
                }
            }
        }

可是我打印出n的值发现冒泡的n值比我写的那个要大,
比如{2,6,4,7,0,1,3,4,5,8,9,0}
冒泡n==26
下面那个n==21。
很疑惑,为什么要前后两个两个比较,相比下面那种有什么优势

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

7条回答 默认 最新

  • catik 2015-04-25 02:24
    已采纳

    你写的这种应该叫做选择排序,每次遍历选出最大的那个放到最后面,跟冒泡排序有一定的区别,
    选择排序交换次数比冒泡排序较少,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。
    原地操作几乎是选择排序的唯一优点,当方度(space complexity)要求较高时,可以考虑选择排序;实际适用的场合非常罕见。

    点赞 评论
  • 菩提九子 2015-04-24 13:35

    i--是先使用i,再进行减。而--i是先减再使用i

    点赞 评论
  • FLY_Fan 2015-04-24 13:37

    你用的不是冒泡排序, 你的是简单选择排序, 有没有看到上面冒泡排序判断交换层只关于 j 在比较,这样冒泡每走一趟序列都将更加有序。

    任何一本《数据结构》书上都有的, 想详细了解的话可以看看。

    点赞 评论
  • 毕小宝 2015-04-24 22:20

    二楼正解。是的,看算法先了解其思想基础,然后才是代码实现的。祝好!

    点赞 评论
  • 浪前青山 2015-04-25 00:01

    算法思想:冒泡排序的基本思想就是不断比较相邻的两个数,让较大的元素不断地往后移。经过一轮比较,就选出最大的数;经过第2轮比较,就选出次大的数,以此类推。
    算法总结及实现
    对于具有N个元素的数组R[n],进行最多N-1轮比较;
    第一轮,逐个比较(R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ……. (R[N-1], R[N]) ; 最大的元素会被移动到R[N]上。
    第二轮,逐个比较(R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ……. (R[N-2], R[N-1]);第二大元素会被移动到R[N-1]上。
    代码是算法思想的体现,你怎么设计算法的,代码就能体现出来。

    点赞 评论
  • Trent1985 2015-04-25 00:42

    所谓冒泡就是一楼说的,前后比较,大的就一个就继续 向后比较,就像冒泡一样,执行一遍循环后大的总是会冒出来的。你需要了解一下冒泡的算法了。

    点赞 评论
  • 没伞的孩子只能跑 2015-04-25 01:40

    其实,你写的和原本的那个是没有区别的。至于输出的n值是由条件成立之后交换次数决定的。也就是说如果你给的初始数组不同,也有可能你写的方法输出的n值更大

    点赞 评论

相关推荐 更多相似问题