A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 王陶成 中级黑马   /  2012-9-3 09:11  /  2140 人查看  /  9 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 王陶成 于 2012-9-3 10:17 编辑

毕老师在讲冒泡的时候提到,可以这样排序:如果两个元素需要换位置,可以不换,将需要换位置的角标和数据记录下来,记录在栈内存中,然后再往后面比,比到最后,找到最大值,将最大值和最后一个值换位置就可以了,将最大值放在后面。将在堆内存中频繁的换位置转移到栈内存中
这样比较该怎样实现呢,讲一下思路。
这样的比较是不是效率会高一点

评分

参与人数 1技术分 +1 收起 理由
王德升 + 1 希望继续努力!

查看全部评分

9 个回复

倒序浏览
本帖最后由 孙沛 于 2012-9-3 09:28 编辑

思路:
你首先要明白int[] arr = new int[5];这句话是栈内存中一个arr变量,引用了堆内存中的一个含有5个元素的内存对象
这种冒泡排序有两种方法:1.是在堆内存中调换元素的位置。2.是在栈内存中调换变量指针的位置
调换栈内存中的变量的位置,实际上是改变了引用的位置,实际上堆内存中的对象位置没有改变,只是呈现给你看时,已经排好了顺序。
效率嘛,肯定是栈排序快了,因为直接是调整的是指针的顺序
回复 使用道具 举报
如果是研究冒泡排序,就不要执着于效率了,要效率就研究快速排序和希尔排序吧.对于冒泡排序,只要懂的写法(最好也要懂原理),过的了笔试就可以了.
回复 使用道具 举报
冒泡排序(BubbleSort)的基本概念是:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,将最大的数放到了最后。在第二趟:仍从第一对数开始比较(因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),第二趟结束,在倒数第二的位置上得到一个新的最大数(其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。
回复 使用道具 举报
孙沛 发表于 2012-9-3 09:25
思路:
你首先要明白int[] arr = new int[5];这句话是栈内存中一个arr变量,引用了堆内存中的一个含有5个元 ...

谢谢,了解了。
回复 使用道具 举报
我做出来了谢谢
回复 使用道具 举报
冒泡排序法的原理是:比较相邻的两个元素,如果符合条件换位置
每次循环结束后,都会有一个最值(较大值或者较小值)被扔到后面,所以下次参与比较的元素会减少一个
角标的最值出现在最后面的位置

冒泡排序,是数组中排序方式的一种,不是最有效的排序。
最有效的排序是直接用 sort()方法,
请参考 api    帮助文档  import  java.util.*;中Arrays的一系列排序的方法,java已经给我们做好了 好多排序方法,我们直接用就ok了。
回复 使用道具 举报
     这个问题的思路我认为是这样的,栈内存里存放的是引用地址和临时变量,堆中才真真的存放数组元素,数组只是个引用而已。而现在我们比较的是两个数组里元素的大小然后换位置,具体到现在的冒泡,它的目的就是一轮找出最大的数并放在最后,如果是两个数比较一下然后互换,我于我们的目的来说必定会浪费资源和时间,所要我们可以改为只互换值的角标,或者只是只记住现在较大值的角标,等最后比完性换到最后。这样的效率也是最高的。
回复 使用道具 举报
本帖最后由 赵森羊 于 2012-9-3 22:02 编辑

原理:
定义变量m记录最值角标。
让参与外循环元素的第一个角标元素跟其余元素的最小值调换位置。
a为去跟其余元素最值调换位置的元素角标,b为跟最值比大小的元素角标。m为最值角标。
代码:
public static void sort(int[]x)
{
        for (int a=0;a<x.length-1 ;a++ )
        {        
                 int m=a;              
                 for (int b=a+1;b<x.length ;b++ )
                 {
                       if (x[m]>x)
                        m=b;
                  }
                 int tmp=x[m];
                 x[m]=x[a];
                 x[a]=tmp;//内循环一次,才调换位置,适当降低了内存消耗
           }
}

其中我实验了那个max的取值,m这个变量存储参与外循环的元素中最小值的角标。因为这个值的范围随着a变化,所以必须取值为a。

回复 使用道具 举报
王陶成 发表于 2012-9-3 10:12
谢谢,了解了。

方法存在漏洞。
我看完那段视频也考虑过这个问题。我说说我的想法。
2L的思想有个弊端,返回值一定为void,因为他是记录了排序后的角标顺序,而数组却还是原来的顺序。
如果函数没有要求打印,而只是要返回一个int[] 呢?
所以,我认为正确的思路应该是:
1.通过嵌套循环来控制比较次数(同普通冒泡排序)
2.定义一个变量temp,来记录该次内循环中最大元素的角标,每一轮内循环开始前赋值temp为0,然后内循环开始,如果有元素大于 temp角标上的元素,那么把该值的角标赋值给temp。
3.每结束一个内循环,将该轮内循环最右边的元素和 角标为temp的元素进行互换。

如此一来,和原来的冒泡排序相比,将大量在堆内存中完成的元素互换,变为了在栈内存中的变量赋值,只是每个内循环结束才需要在堆内存中进行值的互换。
而且程序执行完毕就可以直接returned int[]  
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马