原始的冒泡排序相对而言是非常耗时的,即使一个数组经过几轮交换已经变的有序了,例如[2,1,3,4,5,6,7]这个数组,经过第一轮,已经变成有序的了,但顽固的冒泡还是要继续进行没有营养的两两比较,从而牺牲了时间。
如果用一个flag来判断一下,当前数组是否已经有序,如果有序就退出循环,这样可以明显的提高冒泡排序的表现~
由于冒泡排序的时间复杂度为O(n*n)所以当数据越多的时候,越慢,非常不适合大数据的排序,所以我们测试的时候也是用的长度为800的随机数组。
代码如下:
package go.derek;
import java.util.*;
public class Sort {
//冒泡排序
public void bubbleSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
for(int j=arr.length-1;j>i;j--){
if(arr[j]<arr[j-1]){
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}
}
}
}
//冒泡排序的改良版
public void bubbleSort_plus(int[] arr){
boolean flag=true;
for(int i=0;i<arr.length-1&&flag;i++){
flag=false;
for(int j=arr.length-1;j>i;j--){
if(arr[j]<arr[j-1]){
flag=true;
int tmp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=tmp;
}
}
}
}
public static void main(String[] args){
Sort s=new Sort();
int[] arr1=new int[800];
for(int i=0;i<arr1.length;i++){
arr1[i]=new Random().nextInt(800)+1;
}
int[] arr2=new int[800];
for(int i=0;i<arr2.length;i++){
arr2[i]=new Random().nextInt(800)+1;
}
long n=System.currentTimeMillis();
s.bubbleSort_plus(arr1);
long m=System.currentTimeMillis();
System.out.println("冒泡排序耗时:"+(m-n)+"ms");
long a=System.currentTimeMillis();
s.bubbleSort_plus(arr2);
long b=System.currentTimeMillis();
System.out.println("优化之后耗时:"+(b-a)+"ms");
}
}
多次运行之后发现了效果最明显的一次结果:
冒泡排序耗时:12ms
优化之后耗时:4ms
可以这个flag的重要性哦~
分享到:
相关推荐
冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能 冒泡排序和快速排序的时间性能
python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的python冒泡排序优化后的...
冒泡排序的优化算法,减少时间和次数,引入布尔函数
对冒泡排序法进行优化,比较的次数减少,效率提高
用java 编写的冒泡排序算法,并涵盖了冒泡排序算法的几种优化方式,以及在冒泡排序上的二分查找法。
php优化版本的冒泡排序算法
冒泡排序和快速排序的时间性能比较 冒泡排序和快速排序的时间性能比较 冒泡排序和快速排序的时间性能比较 冒泡排序和快速排序的时间性能比较
1冒泡排序 2改进的冒泡排序,在一次冒泡的过程中,如果没有发生交换,则已经有序 3进一步改进的冒泡排序,如果在某次冒泡过程中,最后一次进行交换的位置为flag,则表示flag之后的序列已经有序,那么下一次冒泡就...
S7-200SMART冒泡排序-优化版(可选择升序降序及数据类型等)
冒泡排序可视化,冒泡排序动画版,模拟了冒泡排序的过程,直观展现冒泡排序的全过程,还是非常富有创意的。
delphi冒泡排序法及性能测试(测试指定数量元素使用冒泡排序所需时间)
js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序js冒泡排序...
冒泡排序详解,简单而详细的讲清楚了,什么是冒泡排序。 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首...
C语言冒泡排序C语言冒泡排序C语言冒泡排序
初学LabelView写的冒泡排序。 随机产生数组元素,并进行冒泡排序。
C++中的冒泡排序 C++中的冒泡排序C++中的冒泡排序C++中的冒泡排序C++中的冒泡排序 C++中的冒泡排序 C++中的冒泡排序 C++中的冒泡排序
C++实现冒泡排序,多层次,快速实现排序算法
本文和大家分享一个基于C语言优化冒泡排序的核心代码。
冒泡排序和选择排序均用两种方法实现,原始方法和在原始方法上的改进和优化,对应博客地址:http://blog.csdn.net/ns_code/article/details/20065107