Java常用的經典排序演算法：冒泡排序與選擇排序

 一、冒泡排序                            

冒泡排序（Bubble Sort）是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止。

　　進一步理解為（假設由小到大排序）：對於給定的n個記錄，從第一個記錄開始依次對相鄰的兩個記錄進行比較，當前面的記錄大於後面的記錄時，交換位置，進行一輪比較和換位後，n個記錄的最大記錄將位於第n位；然後對（n-1）個記錄進行第二輪比較；重覆該過程直到進行比較的記錄只剩下一個為止。

以數組int[] arr = {3,9,5,7,1}為例，冒泡排序的具體步驟如下：

初始狀態：[3,9,5,7,1]

第一趟排序過程如下：

第一次arr[0]=3與arr[1]=9比較交換後： [3,9,5,7,1]

第二次arr[1]=9與arr[2]=5比較交換後： [3,5,9,7,1]

第三次arr[2]=9與arr[3]=7比較交換後： [3,5,7,9,1]

第四次arr[3]=9與arr[4]=1比較交換後：[3,5,7,1,9]

第一趟排序最值9出現在最後一位。

第一趟排序後9出現在第n位：[3,5,7,1,9]

第二趟排序後7出現在n-1位：[3,5,1,7,9]

第三趟排序後5出現在n-2位：[3,1,5,7,9]

第四趟排序後3出現在n-3位，完成排序：[1,3,5,7,9]

程式示例如下（假設由小到大排序）：

package com.bhyj;

public class ArraySort {

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] arr) {
        /**
         * 外迴圈控制排序趟數 
         * 總共需要arr.length-1趟
         */
        for (int i = 0; i < arr.length - 1; i++) {
            /**
             * 內迴圈控制每一趟的比較次數 
             * 第1趟比較次數為arr.length-1 
             * 第2趟比較次數為arr.length-1-1
             * 第3趟比較次數為arr.length-1-2 
             * 第i趟比較次數為arr.length-1-(i-1)
             * 由於i從0開始，所以第i趟比較次數為arr.length-1-i
             * 
             */
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 3, 9, 5, 7, 1 };
        // 排序前
        System.out.print("排序前：");
        printArray(arr);
        // 排序
        ArraySort.bubbleSort(arr);
        System.out.println("");
        // 排序後
        System.out.print("排序後：");
        printArray(arr);

    }

    /**
     * 列印數組
     */
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if(i < arr.length-1){
                System.out.print(",");
            }
        }
        System.out.print("]");
    }

}

輸出結果為：

排序前：[3,9,5,7,1]
排序後：[1,3,5,7,9]

冒泡排序時間複雜度:O(n²)

 二、選擇排序   

　　選擇排序（selection Sort）的基本思想為（假設由小到大排序）：對於給定的一組記錄，經過第一輪比較後得到最小的記錄，然後將該記錄與第一個記錄的位置進行交換；接著對不包括第一個記錄以外的其他記錄進行第二輪比較，得到的最小的記錄與第二個記錄進行位置交換；重覆該過程，直到進行比較的記錄只有一個為止。

以數組int[] arr = {3,9,5,7,1}為例，選擇排序的具體步驟如下：

初始狀態：[3,9,5,7,1]

第一趟排序過程如下：

第一次arr[0]=3與arr[1]=9比較交換後： [3,9,5,7,1]

第二次arr[0]=3與arr[2]=5比較交換後： [3,9,5,7,1]

第三次arr[0]=3與arr[3]=7比較交換後： [3,9,5,7,1]

第四次arr[0]=3與arr[4]=1比較交換後： [1,9,5,7,3]

第一趟排序最值1出現在第一位。

第一趟排序後1出現在第1位：[1,9,5,7,3]

第二趟排序後3出現在第2位：[1,3,9,7,5]

第三趟排序後5出現在第3位：[1,3,5,9,7]

第四趟排序後7出現在第4位，9排在最後一位，完成排序：[1,3,5,7,9]

程式示例如下（假設由小到大排序）：

package com.bhyj;

public class ArraySort {

    /**
     * 選擇排序
     */
    public static void selectSort(int[] arr) {
        /**
         * 外迴圈控制排序趟數 
         * 總共需要arr.length-1趟
         */
        for (int i = 0; i < arr.length - 1; i++) {
            /**
             * 內迴圈控制每一趟的比較次數 
             */
            for (int j = i+1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 3, 9, 5, 7, 1 };
        // 排序前
        System.out.print("排序前：");
        printArray(arr);
        // 排序
        ArraySort.selectSort(arr);
        System.out.println("");
        // 排序後
        System.out.print("排序後：");
        printArray(arr);

    }

    /**
     * 列印數組
     */
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if(i < arr.length-1){
                System.out.print(",");
            }
        }
        System.out.print("]");
    }
}

輸出結果為：

排序前：[3,9,5,7,1]
排序後：[1,3,5,7,9]

選擇排序時間複雜度:O(n²)

關註微信公眾號【Java典籍】，收看更多java技術乾貨

　▼微信掃一掃下圖↓↓↓二維碼關註