這篇文章主要為大家詳細介紹了java簡單冒泡排序實例，具有一定的參考價值，有興趣的小夥伴們可以參考一下
一、演算法原理
#比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數字。
針對所有的元素重複以上的步驟，除了最後一個。
持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
二、實現想法
以二重循環實現，外部循環變數設為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就重複前面二步，否則排序完成。
三、程式碼實作
package sort;
import java.util.Arrays;
/**
* 冒泡排序
* 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
* 针对所有的元素重复以上的步骤，除了最后一个。
* 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
*/
public class BubbleSort {
public static void bubbleSort(int[] arr) {
boolean flag=true;
while (flag) {
flag=false;
int temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { //交换两数位置
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag=true;
}
}
if (!flag){
break;
}
}
}
}
public static void main(String[] args){
int a[]=new int[]{345,22,43,12,65,335,124,636,3};
BubbleSort.bubbleSort(a);
System.out.print(Arrays.toString(a));
}
}四、效能分析
若記錄序列的初始狀態為"正序"，則冒泡排序過程只需進行一趟排序，在排序過程中只需進行n-1次比較，且不移動記錄；反之，若記錄序列的初始狀態為"逆序"，則需進行n（n-1)/2次比較和記錄移動。因此冒泡排序總的時間複雜度為O(n*n)。
五、演算法最佳化
冒泡排序法存在的不足及改進方法：
第一、在排序過程中，執行完最後的排序後，雖然資料已全部排序完備，但程式無法判斷是否完成排序，為了解決這一不足，可設定一個標誌位flag，將其初始值設為true，表示被排序的表是一個無序的表，每一次排序開始前設定flag值為true，在進行資料交換時，修改flag為false。在新一輪排序開始時，檢查此標誌，若此標誌為false，表示上一次沒有做過交換數據，則結束排序；否則進行排序；
第二、在冒泡排序中，一趟掃描有可能無資料交換，也有可能有一次或多次資料交換，在傳統的冒泡排序演算法及近年來的一些改進的演算法中，只記錄一趟掃描有無資料交換的信息，對資料交換發生的位置資訊則不予處理。為了充分利用這個訊息，可以在一趟全域掃描中，對每一反序資料對進行局部冒泡排序處理，稱之為局部冒泡排序。局部冒泡排序與冒泡排序演算法具有相同的時間複雜度，且在正序和逆序的情況下，所需的關鍵字的比較次數和移動次數完全相同。由於局部冒泡排序和冒泡排序的資料移動次數總是相同的，而局部冒泡排序所需關鍵字的比較次數常少於冒泡排序，這意味著局部冒泡排序很可能在平均比較次數上對冒泡排序有所改進，當比較次數較少的優點不足以抵消其程序複雜度所帶來的額外開銷，而當數據量較大時，局部冒泡排序的時間性能則明顯優於冒泡排序。對於N個無序數據，我們在進行一趟冒泡排序時，如果第k個數據和第k+1個數據逆序，那麼對第k+1個數據進行一趟向前的冒泡排序，使其移動到適當的位置，也就是說讓前面k+1個資料調節為正序。因為這個冒泡法只對前k+1個資料冒泡處理，所以我們稱它為－局部冒泡
package sort;
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] arr) {
boolean flag=true;
while (flag) {
flag=false;
int temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) { //交换两数位置
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag=true;
}
}
if (!flag){
break;
}
}
}
}
public static void main(String[] args){
int a[]=new int[]{345,22,43,12,65,335,124,636,3};
BubbleSort.bubbleSort(a);
System.out.print(Arrays.toString(a));
}
}以上是Java中冒泡排序的簡單實例解析的詳細內容。更多資訊請關注PHP中文網其他相關文章！
