Java排序算法总结之冒泡排序
(福利推荐:你还在原价购买阿里云服务器?现在阿里云0.8折限时抢购活动来啦!4核8G企业云服务器仅2998元/3年,立即抢购>>>:9i0i.cn/aliyun)
本文实例讲述了Java排序算法总结之冒泡排序。分享给大家供大家参考。具体分析如下:
前言:冒泡排序(BubbleSort)就是依次比较相邻的两个数,将小数放在前面,大数放在后面。
下面让我们一起 来看冒泡排序在Java中的算法实现。
冒泡排序是计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点:
1.“编程复杂度”很低,很容易写出代码;
2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列,而堆排序、快速排序均不具有稳定性。
不过,一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快,且具有稳定性,但速度不及堆排序、
快速排序。冒泡排序是经过n-1趟子排序完成的,第i趟子排序从第1个数至第n-i个数,若第i个数比后一个数大
(则升序,小则降序)则交换两数。
冒泡排序算法稳定,O(1)的额外的空间,比较和交换的时间复杂度都是O(n^2),自适应,对于已基本排序的算法,时间复杂度为O(n)。冒泡算法的许多性质和插入算法相似,但对于系统开销高一点点。
排序过程
设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。
代码实现:
// 冒泡排序 public class BubbleSort{ public static void sort(Comparable[] data){ // 数组长度 int len = data.length; for (int i = 0; i < len - 1; i++){ // 临时变量 Comparable temp = null; // 交换标志,false表示未交换 boolean isExchanged = false; for (int j = len - 1; j > i; j--){ // 如果data[j]小于data[j - 1],交换 if (data[j].compareTo(data[j - 1]) < 0){ temp = data[j]; data[j] = data[j - 1]; data[j - 1] = temp; // 发生了交换,故将交换标志置为真 isExchanged = true; }// end if }// end for // 本趟排序未发生交换,提前终止算法,提高效率 if (!isExchanged){ return; }// end if }// end for }// end sort public static void main(String[] args){ // 在JDK1.5版本以上,基本数据类型可以自动装箱 // int,double等基本类型的包装类已实现了Comparable接口 Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 }; sort(c); for (Comparable data : c){ System.out.println(data); } } }
使用冒泡排序法对n个数据进行排序,共需要进行n-1次的比较。如果本来就是有顺序的数据,也需要进行n-1次比较。冒泡排序法的算法很简单,效率也较差。
希望本文所述对大家的java程序设计有所帮助。
相关文章
详解spring applicationContext.xml 配置文件
本篇文章主要介绍了详解spring applicationContext.xml 配置文件 ,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧2017-02-02springboot启动的注意事项之不同包下有同样名字的class类问题
这篇文章主要介绍了springboot启动的注意事项之不同包下有同样名字的class类问题,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教2023-06-06Mybatis中BindingException异常的产生原因及解决过程
BindingException异常是MyBatis框架中自定义的异常,顾名思义指的是绑定出现问题,下面这篇文章主要给大家介绍了关于MyBatis报错BindingException异常的产生原因及解决过程,需要的朋友可以参考下2023-06-06
最新评论