一、冒泡排序：
利用冒泡排序對數組進行排序
二、基本概念：
依次比較相鄰的兩個數，將小數放在前面，大數放在後面。即在第一趟：首先比較第1個和第2個數，將小數放前，大數放後。然後比較第2個數和第3個數，將小數放前，大數放後，如此繼續，直至比較最後兩個數，將小數放前，大數放後。至此第一趟結束，將最大的數放到了最後。在第二趟：仍從第一對數開始比較（因為可能由於第2個數和第3個數的交換，使得第1個數不再小於第2個數），將小數放前，大數放後，一直比較到倒數第二個數（倒數第一的位置上已經是最大的），第二趟結束，在倒數第二的位置上得到一個新的最大數（其實在整個數列中是第二大的數）。如此下去，重復以上過程，直至最終完成排序。
三、實現思路：
用二重循環實現，外循環變量設為i，內循環變量設為j。假如有n個數需要進行排序，則外循環重復n-1次，內循環依次重復n-1，n-2，...，1次。每次進行比較的兩個元素都是與內循環j有關的，它們可以分別用a[j]和a[j+1]標識，i的值依次為1,2,...,n-1，對於每一個i，j的值依次為0,1,2,...n-i 。
設數組長度為N：
1．比較相鄰的前後二個數據，如果前面數據大於後面的數據，就將二個數據交換。
2．這樣對數組的第0個數據到N-1個數據進行一次遍歷後，最大的一個數據就“沉”到數組第N-1個位置。
3．N=N-1，如果N不為0就重復前面二步，否則排序完成。
四、java代碼實現：
package 冒泡排序;
import java.util.Arrays;
/**
* 冒泡排序
* @author mmz
*
*/
public class BubbleSort {
public static void BubbleSort(int[] arr) {
int temp;//定義一個臨時變量
for(int i=0;i<arr.length-1;i++){//冒泡趟數
for(int j=0;j<arr.length-i-1;j++){
if(arr[j+1]<arr[j]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
int arr[] = new int[]{1,6,2,2,5};
BubbleSort.BubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
}
五、性能分析：
若記錄序列的初始狀態為"正序"，則冒泡排序過程只需進行一趟排序，在排序過程中只需進行n-1次比較，且不移動記錄；反之，若記錄序列的初始狀態為"逆序"，則需進行n(n-1）/2次比較和記錄移動。因此冒泡排序總的時間復雜度為O(n*n)。
六、算法優化：
冒泡排序法存在的不足及改進方法：
第一，在排序過程中，執行完最後的排序後，雖然數據已全部排序完備，但程序無法判斷是否完成排序，為了解決這一不足，可設置一個標志位flag，將其初始值設置為非0，表示被排序的表是一個無序的表，每一次排序開始前設置flag值為0，在進行數據交換時，修改flag為非0。在新一輪排序開始時，檢查此標志，若此標志為0，表示上一次沒有做過交換數據，則結束排序；否則進行排序；
package 冒泡排序;
import java.util.Arrays;
/**
* 冒泡排序改進版
* @author mmz
*
*/
public class BubbleSort1 {
public static void BubbleSort(int[] arr) {
boolean flag = true;
while(flag){
int temp;//定義一個臨時變量
for(int i=0;i<arr.length-1;i++){//冒泡趟數，n-1趟
for(int j=0;j<arr.length-i-1;j++){
if(arr[j+1]<arr[j]){
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
if(!flag){
break;//若果沒有發生交換，則退出循環
}
}
}
}
public static void main(String[] args) {
int arr[] = new int[]{1,6,2,2,5};
BubbleSort.BubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
}
第二、在冒泡排序中，一趟掃描有可能無數據交換，也有可能有一次或多次數據交換，在傳統的冒泡排序算法及近年來的一些改進的算法中，只記錄一趟掃描有無數據交換的信息，對數據交換發生的位置信息則不予處理。為了充分利用這一信息，可以在一趟全局掃描中，對每一反序數據對進行局部冒泡排序處理，稱之為局部冒泡排序。局部冒泡排序與冒泡排序算法具有相同的時間復雜度，並且在正序和逆序的情況下，所需的關鍵字的比較次數和移動次數完全相同。由於局部冒泡排序和冒泡排序的數據移動次數總是相同的，而局部冒泡排序所需關鍵字的比較次數常少於冒泡排序，這意味著局部冒泡排序很可能在平均比較次數上對冒泡排序有所改進，當比較次數較少的優點不足以抵消其程序復雜度所帶來的額外開銷，而當數據量較大時，局部冒泡排序的時間性能則明顯優於冒泡排序。對於N個無序數據，我們在進行一趟冒泡排序時，如果第k個數據和第k+1個數據逆序，那麼對第k+1個數據進行一趟向前的冒泡排序，使其移動到合適的位置，也就是說讓前面k+1個數據調節為正序。因為這種冒泡法只對前k+1個數據冒泡處理，所以我們稱它為——局部冒泡
希望本文所述對大家的java程序設計有所幫助。
