Java排序算法总结之冒泡排序
本篇章节讲解Java排序算法总结之冒泡排序。分享给大家供大家参考。具体分析如下: 前言:冒泡排序(BubbleSort)就是依次比较相邻的两个数,将小数放在前面,大数放在后面。 下面让我们一起 来看冒泡排序在Java中的算法实现。 冒泡排序是计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点: 1.“编程复杂度”很低,很容易写出代码; 不过,一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快,且具有稳定性,但速度不及堆排序、 冒泡排序算法稳定,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程序设计有所帮助。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |