原始的冒泡排序相對而言是非常耗時的,即使一個數組經過幾輪交換已經變的有序了,例如[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的重要性哦~