java冒泡排序

一、演算法原理

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。

3. 針對所有的元素重覆以上的步驟，除了最後一個。

4. 持續每次對越來越少的元素重覆上面的步驟，直到沒有任何一對數字需要比較。

二、實現思路

       用二重迴圈實現，外迴圈變數設為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));
    }
}