原始的冒泡排序相對而言是非常耗時的僚碎，即使一個數(shù)組經(jīng)過幾輪交換已經(jīng)變的有序了锅知，例如 [2,1,3,4,5,6,7] 這個數(shù)組脯丝，經(jīng)過第一輪，已經(jīng)變成有序的了宾濒，但頑固的冒泡還是要繼續(xù)進(jìn)行沒有營養(yǎng)的兩兩比較，從而犧牲了時間屏箍。
//冒泡排序
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;
}
}
}
}
冒泡排序的算法優(yōu)化
如果用一個flag來判斷一下绘梦，當(dāng)前數(shù)組是否已經(jīng)有序，如果有序就退出循環(huán)赴魁，這樣可以明顯的提高冒泡排序的表現(xiàn)
由于冒泡排序的時間復(fù)雜度為 O(n2) 所以當(dāng)數(shù)據(jù)越多的時候卸奉，越慢，非常不適合大數(shù)據(jù)的排序颖御。
對于上面的序列我們發(fā)現(xiàn)榄棵，含有10個元素的序列需要45次比較（第一趟9次，第二趟8次潘拱，第三趟7次疹鳄，....... ，第九趟1次）芦岂，那么真的需要45次嗎瘪弓？對于下面的這種序列{1,2,4,5,8,9,10,14,15,13}，使用上面的算法也是45次禽最，但觀察發(fā)現(xiàn)該序列大部分是有序的腺怯，第一趟將15沉底放置最后，得到{1,2,4,5,8,9,10,14,13,15}川无，第二趟將14沉底放置最后呛占，得到{1,2,4,5,8,9,10,13,14,15}，從第三趟到最后一趟都無需再移動舀透，所以那些比較都是徒勞的栓票，因此，我們對上述算法進(jìn)行如下優(yōu)化，減少算法的比較次數(shù)走贪。優(yōu)化的方法就是加一個標(biāo)志位佛猛，記錄本趟比較是否發(fā)生交換，下一趟根據(jù)這個標(biāo)志位坠狡，若上一次沒有交換继找，則本趟比較無需進(jìn)行。
//冒泡排序的改良版
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;
}
}
}
}
總體來說逃沿，冒泡排序的效率是較為低下的婴渡，在數(shù)據(jù)量小的情況下可以使用，否則應(yīng)該選擇其他的排序算法凯亮。
