黑马程序员技术交流社区

标题: 【问题已解决】关于排序的问题 [打印本页]

---

作者: 王陶成    时间: 2012-9-3 09:11
标题: 【问题已解决】关于排序的问题


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

---

作者: 孙沛    时间: 2012-9-3 09:25


思路：
你首先要明白int[] arr = new int[5];这句话是栈内存中一个arr变量，引用了堆内存中的一个含有5个元素的内存对象
这种冒泡排序有两种方法：1.是在堆内存中调换元素的位置。2.是在栈内存中调换变量指针的位置
调换栈内存中的变量的位置，实际上是改变了引用的位置，实际上堆内存中的对象位置没有改变，只是呈现给你看时，已经排好了顺序。
效率嘛，肯定是栈排序快了，因为直接是调整的是指针的顺序

---

作者: AngieFans85    时间: 2012-9-3 09:31
如果是研究冒泡排序,就不要执着于效率了,要效率就研究快速排序和希尔排序吧.对于冒泡排序,只要懂的写法(最好也要懂原理),过的了笔试就可以了.

---

作者: 何要民    时间: 2012-9-3 09:45
冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

---

作者: 王陶成    时间: 2012-9-3 10:12

孙沛 发表于 2012-9-3 09:25
思路：
你首先要明白int[] arr = new int[5];这句话是栈内存中一个arr变量，引用了堆内存中的一个含有5个元 ...

谢谢，了解了。

---

作者: 王陶成    时间: 2012-9-3 10:17
我做出来了谢谢

---

作者: 杨千里    时间: 2012-9-3 10:19
冒泡排序法的原理是：比较相邻的两个元素，如果符合条件换位置
每次循环结束后，都会有一个最值（较大值或者较小值）被扔到后面，所以下次参与比较的元素会减少一个
角标的最值出现在最后面的位置

冒泡排序，是数组中排序方式的一种，不是最有效的排序。
最有效的排序是直接用 sort（）方法，
请参考 api    帮助文档  import  java.util.*；中Arrays的一系列排序的方法，java已经给我们做好了 好多排序方法，我们直接用就ok了。

---

作者: 张飞年    时间: 2012-9-3 10:39
     这个问题的思路我认为是这样的，栈内存里存放的是引用地址和临时变量，堆中才真真的存放数组元素，数组只是个引用而已。而现在我们比较的是两个数组里元素的大小然后换位置，具体到现在的冒泡，它的目的就是一轮找出最大的数并放在最后，如果是两个数比较一下然后互换，我于我们的目的来说必定会浪费资源和时间，所要我们可以改为只互换值的角标，或者只是只记住现在较大值的角标，等最后比完性换到最后。这样的效率也是最高的。

---

作者: zhaosenyang    时间: 2012-9-3 22:01


原理：
定义变量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-4 00:15

王陶成 发表于 2012-9-3 10:12
谢谢，了解了。

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

如此一来，和原来的冒泡排序相比，将大量在堆内存中完成的元素互换，变为了在栈内存中的变量赋值，只是每个内循环结束才需要在堆内存中进行值的互换。
而且程序执行完毕就可以直接returned int[]  

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2