Java完成冒泡排序算法及對其的簡略優化示例。本站提示廣大學習愛好者：（Java完成冒泡排序算法及對其的簡略優化示例）文章只能為提供參考，不一定能成為您想要的結果。以下是Java完成冒泡排序算法及對其的簡略優化示例正文
道理
冒泡排序年夜概是一切法式員都邑用的算法，也是最熟習的算法之一。
它的思緒其實不龐雜：
設如今要給數組arr[]排序，它有n個元素。
1.假如n=1：明顯不消排了。（現實上這個評論辯論仿佛沒甚麼需要）
2.假如n>1：
（1）我們從第一個元素開端，把每兩個相鄰元素停止比擬，假如後面的元素比前面的年夜，那末在最初的成果外面前者確定排在前面。所以，我們把這兩個元故舊換。然落後行下兩個相鄰的元素的比擬。如斯直到最初一對元素比擬終了，則第一輪排序完成。可以確定，最初一個元素必定是數組中最年夜的（由於每次都把絕對年夜的放到前面了）。
（2）反復上述進程，此次我們無需斟酌最初一個，由於它曾經排好了。
（3）如斯直到只剩一個元素，這個元素必定是最小的，那末我們的排序可以停止了。明顯，停止了n-1次排序。
上述進程中，每次（或許叫做“輪”）排序都邑有一個數從某個地位漸漸“浮動”到終究的地位（畫個表示圖，把數組畫成豎直的便可以看出來），就像冒泡一樣，所以，它被稱為“冒泡排序法”。
代碼完成：
public class BubbleSort{
public static void main(String[] args){
int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
for (int i = 0; i < score.length -1; i++){ //最多做n-1趟排序
for(int j = 0 ;j < score.length - i - 1; j++){ //對以後無序區間score[0......length-i-1]停止排序(j的規模很症結，這個規模其實慢慢減少的)
if(score[j] < score[j + 1]){ //把小的值交流到前面
int temp = score[j];
score[j] = score[j + 1];
score[j + 1] = temp;
}
}
System.out.print("第" + (i + 1) + "次排序成果：");
for(int a = 0; a < score.length; a++){
System.out.print(score[a] + "\t");
}
System.out.println("");
}
System.out.print("終究排序成果：");
for(int a = 0; a < score.length; a++){
System.out.print(score[a] + "\t");
}
}
}
算法機能/龐雜度
我們疏忽失落輪回變量自增和初始化的時光。先剖析算法的比擬次數。輕易看出，下面這類未經任何改良的冒泡排序不管輸出數據若何都邑停止n-1輪排序，而每輪排序須要比擬的次數從n-1遞加到0。那末，總的比擬次數等於 (n-1)+(n-2)+...+2+1 = (n-1)n/2≈(n^2)/2。（因為不曉得這裡若何打出平方，這裡，我用n^2代表平方，下同）
再來看下賦值次數。這裡的賦值是指個中的交流操作，關於上述代碼，1次交流等於三次賦值。因為並不是每次都必需交流，是以，賦值操作的次數與輸出數據相關。最好情形(best case)下，即一開端就是有序的情形下，賦值次數為0。 而最壞情形(worst case)下，賦值次數為(n-1)n/2。假定輸出數據均勻（或許說“完整隨機”）散布，那末年夜約有交流次數為比擬次數的一半。由下面的成果，可以獲得均勻情形(average case)下，賦值次數為 3/2 * (n^2)/2 = 3/4*(n^2).
綜上，不管在何種情形下，冒泡排序空間龐雜度（額定空間）老是O(1)。
改良
在數據完整有序的時刻展示出最優時光龐雜度，為O(n)。其他情形下，簡直老是O(n^2)。是以，算法在數據根本有序的情形下，機能最好。
然則，下面的代碼怎樣能夠湧現O(n)龐雜度呢？現實上，由於下面重視的是根本思緒，是以只是最簡略情形，要使算法在最好情形下有O(n)龐雜度，須要做一些改良，改良後的代碼為：
public static void bubbleSort(int[] arr) {
int temp = 0;
boolean swap;
for (int i = arr.length - 1; i > 0; --i) { // 每次須要排序的長度
swap=false;
for (int j = 0; j < i; ++j) { // 從第一個元素到第i個元素
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swap=true;
}
}//loop j
if (swap==false){
break;
}
}//loop i
}// method bubbleSort
現實上，因為在年夜量數據的情形下簡直不應用冒泡排序，而應用小數據的時刻增長的布爾變量反而會形成額定的開支。所以小我以為下面改良後的算法只是純實際的，平日，冒泡排序就寫後面一種就好了。
算法穩固性
輕易看出，在相鄰元素相等時，我們其實不須要交流它們的地位，所以，冒泡排序是穩固排序。
算法實用場景
冒泡排序思緒簡略，代碼也簡略，特殊合適小數據的排序。然則，因為算法龐雜度較高，在數據量年夜的時刻不合適應用。假如必定要在較多半據的時刻應用，最好對算法加以改良，例如選擇排序法。
