在开始主要内容之前,先说一下为什么会去写这篇文章呢?当然是有原因的。
第一个原因:我和我的同学在学习java的排序过程中,冒泡排序和选择排序傻傻分不清楚。把这两个排序放在一起,可以帮助我们去更好的理解它们。
第二个原因:主要检验下自己自学的成果与问题。
那么好,咱们言归正传,首先说下这个冒泡排序:
冒泡排序:冒泡排序的定义就不提了,总结起来就一句话(划重点):,从左到右,数组中相邻的两个元素进行比较,将较大的放到后面。
我们从下面这个例子中去学习下冒泡排序;
例如:有一个int [] a={2,6,5,3,1};
![image](https://upload-images.jianshu.io/upload_images/3413336-77396f1fa3a8a6a5.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
这个就是用冒泡排序的思路进行的第一轮排序:从图中,不难看出第一轮比较。比较了4次;
第二轮排序开始时的数组已经变成了{2,5,3,1,6}
![image](https://upload-images.jianshu.io/upload_images/3413336-4e2316f47a8afb4f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
因为第一轮已经确定6的位置,所以,第二轮比较是不再需要再去与这个6比较的,从图可以看出,第二轮比较,比较了3次,确定了5的位置;
第三轮排序开始时的数组已经变成了{2,3,1,5,6};
![image](https://upload-images.jianshu.io/upload_images/3413336-b6a38dbfdaeaa30a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
同理,第三轮是不需要去与5进行比较的,从图可以看出,第三轮比较了2次,确定了3的位置。
第四轮排序开始时的数组已经变成了{2,1,3,5,6};
![image](https://upload-images.jianshu.io/upload_images/3413336-7606c41c10411408.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
第4轮比较完之后呢,这组数就已经完全排好了顺序,接下来就需要找规律,去实现下代码了: 运行结果:
到这里呢,冒泡排序就结束了;下面是选择排序,总结一句话就是(划重点):从第一个位置开始比较,找出最小的,和第一个位置互换,开始下一轮。
我们同样,以上面的例子为例 int [] a= {2,6,5,3,1};
![image](https://upload-images.jianshu.io/upload_images/3413336-1dc7a701a641616f.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
从图可以看出,第一轮比较,比较了4轮,找出了最小数1,与第一个位置的数字进行了换位;
第二轮排序开始时的数组已经变成了{1,6,5,3,2};
![image](https://upload-images.jianshu.io/upload_images/3413336-297ba9f0be8c287a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
从图可以看出,第二轮比较,比较了3次,确定剩余数中的最小数为2,与第二个位置的数交换。
第三轮排序开始时的数组已经变成了{1,2,5,3,6};
![image](https://upload-images.jianshu.io/upload_images/3413336-6b405289506a12c3.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
从图可以看出,第三轮比较,比较了2次,确定了剩余数中最小的数3,与第三个位置的数互换位置。
第四轮排序开始时的数组已经变成了{1,2,3,5,6};
![image](https://upload-images.jianshu.io/upload_images/3413336-2421dba42104a747.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
从图可以看出,第四轮比较,比较了1次,确定了剩余数中最小的数5,放在了第4个位置。
这样4轮比较后,这组数已经排序好了,接下来同上,去找规律,实现代码了:
运行结果:
选择排序也就结束了,这样一弄有没有更清楚呢?
那么好,是时候来总结下他们的区别了(划重点)。
(1)冒泡排序是比较相邻位置的两个数,而选择排序是按顺序比较,找最大值或者最小值;
(2)冒泡排序每一轮比较后,位置不对都需要换位置,选择排序每一轮比较都只需要换一次位置;
(3)冒泡排序是通过数去找位置,选择排序是给定位置去找数;
冒泡排序优缺点:优点:比较简单,空间复杂度较低,是稳定的;
缺点:时间复杂度太高,效率慢;
选择排序优缺点:优点:一轮比较只需要换一次位置;
缺点:效率慢,不稳定(举个例子5,8,5,2,9 我们知道第一遍选择第一个元素5会和2交换,那么原序列中2个5的相对位置前后顺序就破坏了)。