黑马程序员技术交流社区

标题: 理解冒泡和选择排序 [打印本页]

---

作者: 然后呢8908    时间: 2015-9-5 23:09
标题: 理解冒泡和选择排序
冒泡和选择（n个数）的第一重循环也就是排序的次数都是一样的，也就是n-1次。
到了第二重循环就不一样了。
冒泡：每一次比较是挨着的两个数比较，将较大的数放在最后。这也是就是为什么他第二重循环比较的次数越来越少了，是到arr.length-1-i;因为后面都已经放了最大的了，所以不用比较。
注意：冒泡排序最主要的是理解排序的原理，就是把大的往里面放。所以比较次数变少。
（冒泡是大往前面放）
public  static void maopaoSort(int[] arr) {
                for (int i = 0; i <arr.length-1; i++) {
                        for (int j = 0; j <arr.length-1-i; j++) {
                                if(arr[j]>arr[j+1]){
                                        int temp=arr[j];
                                        arr[j]=arr[j+1];
                                        arr[j+1]=temp;
                                }
                        }
                }               
        }
选择：他的比较思路就是拿第一个数跟所有的比较，将较小的放在前面，然后拿第二个数跟后面的进行比较，再次把小的放在第二位，依次类推。
（选择是小的往前面跑）
public  static void selectSort(int[] arr) {
                for (int i = 0; i < arr.length-1; i++) {
                        for (int j = i+1; j < arr.length; j++) {
                                if(arr[i]>arr[j]){
                                        int temp=arr[i];
                                        arr[i]=arr[j];
                                        arr[j]=temp;
                                }
                        }
                }       
        }

最后老师给的总结：
按照冒泡排序从小到大实现:9 8 7 6 5
第一趟排序前:9 8 7 6 5   //经过第一趟已经找到了最大的值,放到最底下,同时最小的值向前浮动了一位
        第一次:8 9 7 6 5
        第二次:8 7 9 6 5
        第三次:8 7 6 9 5
        第四次:8 7 6 5 9
       
第二趟排序前:8 7 6 5 9
        第一次:7 8 6 5 9
        第二次:7 6 8 5 9
        第三次:7 6 5 8 9
        第四次:7 6 5 8 9
       
第三趟排序前:7 6 5 8 9
        第一次:6 7 5 8 9
        第二次:6 5 7 8 9
        第三次:6 5 7 8 9
        第四次:6 5 7 8 9
       
第四趟排序前:6 5 7 8 9
        第一次:5 6 7 8 9
        第二次:5 6 7 8 9
        第三次:5 6 7 8 9
        第四次:5 6 7 8 9

仔细分析(数组长度：len=arr.length=5)：
趟数(j)                        次数=len-1-j
0                                4
1                                3
2                                2
3                                1
1.通过上面的分析我们可以发现，5个数总共排序4趟，所以如果有n（就是数组arr的长度arr.length）个数的话，排序为n-1(arr.length-1)趟
所以控制趟数的循环可以写成：
for(int j=0;j<arr.length-1;j++){}注意：j<arr.length-1,代表j只能取到arr.length-2,而j从0开始，所以中间循环的次数为：arr.length-2-(-1)=arr.length-1趟
2.通过上面的分析每趟所循环的次数为len-1-j即arr.length-1-j,而内层循环是比较相邻的两个数，所以变量i要从0开始，这样内层循环就可以写为：
for(int i=0;i<arr.length-1-j;i++){}
3.将上面的外层和内层循环组合即为排序的伪代码：
for(int j=0;j<arr.length-1;j++){
        for(int i=0;i<arr.length-1-j;i++){
                if(arr[i]>arr[i+1]){
                        int temp = arr[i];
                        arr[i] = arr[i+1];
                        arr[i+1] = temp;
                }
        }
}


按照选择拍序从小到大实现:9 8 7 6 5
第一趟排序前:9 8 7 6 5   //拿第一个数和它后面的（第二个到第五个数进行比较）每个数比较，最终获得最小的数放在最前面，而此时最大的数已经向后移动了一个位置
        第一次:8 9 7 6 5（9和8交换）
        第二次:7 9 8 6 5（8和7交换）
        第三次:6 9 8 7 5（7和6交换）
        第四次:5 9 8 7 6（6和5交换）
       
第二趟排序前:5 9 8 7 6  //拿第二个数和它后面的（第三个到第五个数进行比较）每个数比较，最终获得第二小的数数放在第二个位置，而此时最大的数又向后移动了一个位置

        第一次:5 8 9 7 6（9和8交换）
        第二次:5 7 9 8 6（8和7交换）
        第三次:5 6 9 8 7（7和6交换）
        第四次:5 6 9 8 7

       
第三趟排序前:5 6 9 8 7 //拿第三个数和它后面的（第四个到第五个数进行比较）每个数比较，最终获得第三小的数数放在第三个位置，而此时最大的数又向后移动了一个位置
        第一次:5 6 8 9 7（9和8交换）
        第二次:5 6 7 9 8（8和7交换）
        第三次:5 6 7 9 8
        第四次:5 6 7 9 8

       
第四趟排序前:5 6 7 9 8 //拿第四个数和它后面的（第五个到第五个数进行比较）每个数比较，最终获得第四小的数数放在第四个位置，而此时最大的数又向后移动了一个位置
总共五个数，前四个都已经确定好了位置了，最后一个就不用管了
        第一次:5 6 7 8 9（9和8交换）
        第二次:5 6 7 8 9
        第三次:5 6 7 8 9
        第四次:5 6 7 8 9



1.通过上面的分析我们可以发现，5个数总共排序4趟，所以如果有n（就是数组arr的长度arr.length）个数的话，排序为n-1(arr.length-1)趟
所以控制趟数的循环可以写成：
for(int j=0;j<arr.length-1;j++){}注意：j<arr.length-1,代表j只能取到arr.length-2,而j从0开始，所以中间循环的次数为：arr.length-2-(-1)=arr.length-1趟
2.通过上面的分析每趟所进行的内层循环为当前趟数所代表的元素arr[j]和它后面的所有元素（下标从j+1到arr.length-1）进行比较
for(int i=j+1;i<arr.length-1;i++){}
3.将上面的外层和内层循环组合即为排序的伪代码：
for(int j=0;j<arr.length-1;j++){
        for(int i=j+1;i<arr.length-1;i++){
                if(arr[j]>arr[i]){
                        int temp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = temp;
                }
        }
}

---

作者: 弄啥嘞。    时间: 2015-9-5 23:30
虽然会了,但是已经收藏,保存到笔记里面了.谢谢~!

---

作者: 迷茫不堪的年纪    时间: 2015-9-5 23:51
评论完了，慢慢看

---

作者: 18664300701    时间: 2015-9-6 00:11
真的感谢，之前一直明白冒泡，对选择模模糊糊的，现在理解了

---

作者: MilesMatheson    时间: 2015-9-6 00:16
有时候会混淆这两种，谢谢楼主

---

作者: silencea    时间: 2015-9-6 22:10
后面的都学了啊,真快.

---

作者: 魁子    时间: 2015-9-6 22:12
冒泡排序一直是我很纠结的·····

---

作者: 黑马小辛    时间: 2015-9-6 22:12
谢谢分享

---

作者: 然后呢8908    时间: 2015-9-6 22:16

魁子 发表于 2015-9-6 22:12
冒泡排序一直是我很纠结的·····

最主要的是理解。。。

---

作者: benpaodeboluo    时间: 2015-9-6 22:16
谢谢分享...

---

作者: 然后呢8908    时间: 2015-9-6 22:17

黑马小辛 发表于 2015-9-6 22:12
谢谢分享

不用谢，自己学到才是真的

---

作者: stray_cat    时间: 2015-9-6 22:18
太长了，先mark，慢慢看

---

作者: 15706025762    时间: 2015-9-6 22:18
好难 。。。。。。。。。。。。

---

作者: 然后呢8908    时间: 2015-9-6 22:19

弄啥嘞。 发表于 2015-9-5 23:30
虽然会了,但是已经收藏,保存到笔记里面了.谢谢~!

我也是新手，理解了就好。自己写的，写的不好，不要见怪

---

作者: 然后呢8908    时间: 2015-9-6 22:20

迷茫不堪的年纪 发表于 2015-9-5 23:51
评论完了，慢慢看

最主要的是理解

---

作者: 然后呢8908    时间: 2015-9-6 22:21

MilesMatheson 发表于 2015-9-6 00:16
有时候会混淆这两种，谢谢楼主

很多人都这样，主要还是没有理解怎么排序的，希望可以帮到你

---

作者: 然后呢8908    时间: 2015-9-6 22:24

15706025762 发表于 2015-9-6 22:18
好难 。。。。。。。。。。。。

你理解了就不难了

---

作者: 然后呢8908    时间: 2015-9-6 22:25

stray_cat 发表于 2015-9-6 22:18
太长了，先mark，慢慢看

只要看最主要的总结可以理解了

---

作者: 0902赵建新    时间: 2015-9-6 22:31
提前收藏了，快学到这里了。感谢分享。32赞。

---

作者: Andy丶JF    时间: 2015-9-6 22:34
还没学到，好像挺难得样子

---

作者: 李治锋    时间: 2015-9-6 22:38
值得收藏

---

作者: Scorpio丶    时间: 2015-9-6 22:42
先保存下

---

作者: 然后呢8908    时间: 2015-9-6 22:47

0902赵建新 发表于 2015-9-6 22:31
提前收藏了，快学到这里了。感谢分享。32赞。

嗯提前学很好啊，只要理解就好。

---

作者: 然后呢8908    时间: 2015-9-6 22:48

Andy丶JF 发表于 2015-9-6 22:34
还没学到，好像挺难得样子

理解了就真的很简单

---

作者: 青春触及的阳光    时间: 2015-9-6 22:51
就是看到这里开始晕的……

---

作者: 寰宇天侠    时间: 2015-9-6 22:59
还是画图好理解，一个会的给一个不会的画图教着，两下就明白原理了

---

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

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