Java實現常見排序演演算法

排序也稱排序演演算法(Sort Algorithm)，排序是將一組資料，依指定的順序進行排列的過程。排序的分類：

1. 內部排序:指將需要處理的所有資料都載入到內部記憶體中進行排序。

2. 外部排序法：資料量過大，無法全部載入到記憶體中，需要藉助外部儲存進行排序。

3. 常見的排序演演算法分類(見下圖):
   

排序演演算法	平均時間複雜度	最好情況	最壞情況	空間複雜度	排序方式	穩定性
氣泡排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	穩定
選擇排序	O(n^2)	O(n^2)	O(n^2)	O(1)	In-place	不穩定
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	In-place	穩定
希爾排序	O(n log n)	O(n log^2 n)	O(n log ^2n)	O(1)	In-place	不穩定
歸併排序	O(n log n)	O(n log n)	O(n log n)	O(n)	Out-place	穩定
快速排序	O(n log n)	O(n log n)	O(n^2)	O(1)	In-place	不穩定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	In-place	不穩定
計數排序	O(n+k)	O(n+k)	O(n+k)	O(k)	Out-place	穩定
桶排序	O(n+k)	O(n+k)	n^2	O(n+k)	Out-place	不穩定
基數排序	O(n x k)	O(n x k)	O(n x k)	O(n+k)	Out-place	穩定

時間複雜度:一個演演算法執行所耗費的時間。空間複雜度: 執行完一個程式所需記憶體的大小

穩定: 如果 a 原本在 b 前面，而 a=b，排序之後 a仍然在 的前面; 不穩定: 如果 a 原本在 b 的前面，而 a=b，排序之後 a可能會出現在 b 的後面

n: 資料規模
k: 「桶」的個數
In-place: 不佔用額外記憶體
Out-place: 佔用額外記憶體

氣泡排序

氣泡排序（Bubble Sort）是一種簡單的排序演演算法，它重複地遍歷要排序的列表，比較相鄰的兩個元素，並根據需要交換它們的位置，直到整個列表排序完成。氣泡排序的基本思想是將較大的元素逐漸「浮」到列表的末尾。氣泡排序的時間複雜度為O(n^2)，在大型列表和實際應用中效率低下

1. 從列表的第一個元素開始，依次比較相鄰的兩個元素。

2. 如果前一個元素大於後一個元素，則交換它們的位置。

3. 繼續向後遍歷，重複執行步驟 1 和步驟 2，直到遍歷到列表末尾。

4. 重複上述步驟，每次遍歷都將最大的元素「浮」到列表末尾。

5. 重複執行 n-1 次（n 是列表長度），直到整個列表排序完成。

下面是使用 Java 編寫氣泡排序演演算法的範例程式碼：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 外層迴圈控制需要比較的輪數
        for (int i = 0; i < n - 1; i++) {
            // 內層迴圈執行相鄰元素的比較和交換
            // 每輪將最大的元素「冒泡」到末尾
            for (int j = 0; j < n - i - 1; 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 = {4, 3, 5, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("排序後的陣列：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

上面程式碼可以優化：在內層迴圈中如果發生了交換操作，則將 flag 設定為 true。在內層迴圈結束後，檢查 flag 的值來判斷是否發生了交換操作。如果沒有發生交換，則說明列表已經有序，可以提前結束排序過程。
這樣修正後的氣泡排序演演算法可以更準確地判斷列表是否已經有序，並在有序時提前結束排序過程，提高了演演算法的效率。

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean flag = false;
    for (int i = 0; i < n - 1; i++) {
        flag = false; // 將 flag 初始化為 false
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交換相鄰兩個元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true; // 設定 flag 為 true
            }
        }
        if (!flag) {
            break;
        }
    }
}

選擇排序

選擇排序（Selection Sort）是一種簡單直觀的排序演演算法，它的基本思想是每次從未排序的部分中選擇最小（或最大）的元素，並將其與當前位置進行交換，這樣，每一輪遍歷都會將一個元素放到正確的位置上，逐漸形成有序序列。通過不斷重複這個過程，直到整個列表排序完成。時間複雜度為O(n^2)

以下是選擇排序演演算法的基本步驟：

1. 遍歷列表，將第一個元素視為已排序部分。

2. 在未排序部分中找到最小（或最大）的元素。

3. 將找到的最小（或最大）元素與已排序部分末尾的元素進行交換。

4. 將已排序部分末尾向後移動一個位置。

5. 重複上述步驟，直到整個列表排序完成。

範例程式碼：

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        // 外層迴圈控制當前待填入的位置
        for (int i = 0; i < n - 1; i++) {
             // 假設當前位置為最小元素的位置
            int minIndex = i;
            // 內層迴圈找到未排序部分中最小元素的索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交換最小元素和當前位置元素
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        selectionSort(arr);
        System.out.println("排序後的陣列：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

選擇排序是一種原地、穩定、比較類的排序演演算法。它不需要額外空間，並且對於小型資料集或部分有序的資料集，它可能比其他複雜度較低但需要額外空間的演演算法更快。然而，選擇排序的時間複雜度為 O(n^2)，因此在處理大型資料集時效率較低。比氣泡排序是要快一些

插入排序

插入排序（Insertion Sort）是一種簡單直觀的排序演演算法，其基本思想是將一個元素插入到已排序部分的正確位置中，通過不斷地擴大已排序部分的範圍，最終完成整個列表的排序。插入排序的時間複雜度為O(n^2)，因此在處理大型資料集時效率較低

以下是插入排序演演算法的基本步驟：

1. 將列表分為已排序部分和未排序部分。初始時，已排序部分只包含第一個元素，而未排序部分包含剩餘的元素。

2. 從未排序部分中取出第一個元素，並將其插入到已排序部分的正確位置中。為了找到正確位置，可以從已排序部分的末尾開始向前比較，並將較大（或較小）的元素向後移動。

3. 重複步驟 2，直到未排序部分中所有元素都被插入到已排序部分中。

4. 整個列表完成排序。

插入排序演演算法的範例程式碼：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        // 從第二個元素開始，將當前元素插入已排序部分的正確位置
        for (int i = 1; i < n; i++) {
            // 選擇當前元素作為待插入元素
            int key = arr[i];
            int j = i - 1;
            // 從當前元素的前一個元素開始，逐個比較並將較大的元素向後移動
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 將待插入元素放入正確的位置
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println("排序後的陣列：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

希爾排序

希爾排序（Shell Sort）是一種基於插入排序的排序演演算法，也被稱為「縮小增量排序」（Diminishing Increment Sort）。它通過將整個列表分割成多個較小的子序列，並對這些子序列進行插入排序，從而逐步減少排序的範圍，最終完成整個列表的排序。希爾排序在提供了一種平衡了效能和簡單性的排序方法。

希爾排序的基本思想是通過預排序來減小逆序數的數量。逆序數是指在一個列表中，有兩個元素的相對順序與期望的排序順序不符的情況。通過首先以較大的步長進行預排序，可以顯著減少逆序數的數量，從而提高後續插入排序的效率。

以下是希爾排序演演算法的基本步驟：

1. 選擇一個增量序列（通常為一個遞減的數列），用來分割原始列表。

2. 對每個增量分割出的子序列進行插入排序，也就是將子序列的元素按照插入排序的方式排好序。

3. 逐步縮小增量，重複步驟 2，直到增量為 1，此時整個列表被排序完成。

希爾排序演演算法的範例程式碼：

public class Shell {
     public static void shellSort(int[] arr) {
        int n = arr.length;

        // 選擇增量序列，通常為 n/2，n/4，...，1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 對每個子序列進行插入排序
            for (int i = gap; i < n; i++) {
                // 當前待插入元素
                int temp = arr[i];
                int j = i;

                // 插入排序步驟
                while (j >= gap && arr[j - gap] > temp) {
                    // 向後移動元素
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                // 將待插入元素放入正確位置
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
        shellSort(arr);
        System.out.println("排序後的陣列：");
        System.out.print(Arrays.toString(arr));
    }
}

在這段程式碼中，我們定義了一個 shellSort 方法來執行希爾排序。在每次排序中，我們根據增量序列將列表分割成多個子序列，並對每個子序列進行插入排序。逐步減小增量，直至增量為 1，完成整個排序過程。

希爾排序的時間複雜度取決於所選擇的增量序列，通常在平均情況下為 O(nlogn)。儘管希爾排序並不是最快的排序演演算法，但在某些情況下，特定的增量序列可以使其效能相當不錯。希爾排序是一種原地、不穩定、比較類的排序演演算法，在一些特定場景下可以提供較好的效能。

快速排序

快速排序（Quick Sort）是一種高效的排序演演算法，它採用分治策略，通過將一個大問題分解為小問題來排序整個陣列。快速排序的基本思想是選擇一個「基準」元素，然後將陣列分成兩個子陣列，一個子陣列中的所有元素小於基準，另一個子陣列中的所有元素大於基準。然後，遞迴地對這兩個子陣列進行排序，最終得到有序的陣列。

快速排序的基本步驟如下：

1. 選擇基準元素：從待排序陣列中選擇一個元素作為基準（pivot）。通常情況下，可以選擇第一個元素、最後一個元素或者中間元素作為基準。

2. 分割操作：將陣列分割成兩個子陣列，一個子陣列中的所有元素小於基準，另一個子陣列中的所有元素大於基準。這個過程稱為分割操作。

3. 遞迴排序：對兩個子陣列遞迴地應用快速排序演演算法。即對小於基準的子陣列和大於基準的子陣列分別進行快速排序。

4. 合併結果：將經過排序的兩個子陣列合併成最終的有序陣列。

快速排序的關鍵在於選擇合適的基準元素和分割操作。通過不斷地將陣列分割成較小的子陣列，並對子陣列進行排序，最終實現整個陣列的有序性。快速排序平均時間複雜度為O(nlogn)，效能比氣泡排序和插入排序要好得多。

程式碼範例

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找到基準元素的正確位置並進行分割
            int pivotIndex = partition(arr, low, high);

            // 遞迴地對基準元素的左右子陣列進行排序
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        // 選擇基準元素（可以選擇第一個元素、最後一個元素或中間元素）
        int pivot = arr[high];

        // 初始化分割索引
        int i = low - 1;

        // 遍歷陣列，將小於基準的元素移到分割索引的左側
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                // 交換元素，將小於基準的元素移到分割索引的左側
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 將基準元素放入正確的位置
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        // 返回基準元素的位置
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("排序後的陣列：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

先定義了一個quickSort函數，它接受一個陣列和兩個表示要排序部分的開始和結束的索引。然後，它呼叫partition函數，該函數選擇一個基準元素並將所有比它小的元素移動到其左邊，比它大的元素移動到其右邊。然後，quickSort函數對基準的左右兩側分別進行獨立的相同操作。最後，主函數建立了一個需要排序的陣列，並呼叫quickSort函數進行排序，然後列印出排序後的陣列

歸併排序

歸併排序是一種經典的排序演演算法，它採用分治法的思想，將一個大問題分解為多個小問題，然後將小問題的解合併起來得到最終的解。歸併排序的基本思想是將待排序的陣列不斷地二分，直到每個子陣列只有一個元素，然後再將這些子陣列兩兩合併成一個有序的陣列，最終得到完全有序的陣列。

歸併排序的步驟如下：

1. 分割階段：

   • 將待排序的陣列從中間分成兩個子陣列，分別是左子陣列和右子陣列。

   • 遞迴地對左子陣列和右子陣列進行分割，直到每個子陣列只剩一個元素。

2. 合併階段：

   • 對已經分割好的子陣列進行合併，將它們合併成一個有序的陣列。

   • 建立一個臨時陣列，用來存放合併後的結果。

   • 初始化三個指標：一個指向左子陣列的當前元素，一個指向右子陣列的當前元素，一個指向臨時陣列的當前位置。

   • 依次比較左右子陣列的當前元素，將較小的元素放入臨時陣列，並將相應的指標向後移動。

   • 重複上述步驟，直到某個子陣列的元素全部放入臨時陣列中。

3. 複製剩餘元素：

   • 當某個子陣列的元素全部放入臨時陣列後，可能另一個子陣列還有剩餘元素。

   • 將剩餘元素依次複製到臨時陣列的末尾。

4. 拷貝回原陣列：

   • 合併完成後，臨時陣列中存放著完全有序的元素。

   • 將臨時陣列中的元素拷貝回原始陣列的相應位置，完成排序。

5. 遞迴終止：

   • 繼續遞迴地分割和合並，直到所有子陣列都變成只有一個元素，此時排序完成。

程式碼範例

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right){
            int mid = (left + right) / 2; // 計算中間索引
            mergeSort(arr, left, mid);// 對左半部分進行遞迴排序
            mergeSort(arr, mid + 1, right);// 對右半部分進行遞迴排序
            merge(arr,left,mid,right);// 合併左右兩部分的有序子陣列
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1; // 左子陣列的長度
        int n2 = right - mid; // 右子陣列的長度
        int[] leftArr = new int[n1];// 建立左子陣列
        int[] rightArr = new int[n2];// 建立右子陣列

        // 將原始陣列中的元素複製到左子陣列
        for (int i = 0; i < n1; i++) {
           leftArr[i] = arr[left + i];
        }

        // 將原始陣列中的元素複製到右子陣列
        for (int j = 0; j < n2; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }

        int i = 0,j = 0; // 初始化左子陣列和右子陣列的索引
        int k = left; // 初始化原始陣列的索引，從左邊界開始

        // 比較左右兩個子陣列的元素，並將較小的元素放入原始陣列中
        while (i < n1 && j < n2){
            if (leftArr[i] <= rightArr[j]){
                arr[k] = leftArr[i];
                i++;
            }else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // 如果左子陣列還有剩餘元素，將其全部複製到原始陣列中
        while (i < n1){
          arr[k] = leftArr[i]; // 將剩餘的左子陣列元素複製到原始陣列中
          i++;
          k++;
        }
        // 如果右子陣列還有剩餘元素，將其全部複製到原始陣列中
        while (j < n2){
            arr[k] = rightArr[j];// 將剩餘的右子陣列元素複製到原始陣列中
            j++;
            k++;
        }

    }
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 0, 4, 6, 5 ,10,89,69,19};
        int n = arr.length;

        mergeSort(arr, 0, n - 1);

        System.out.println("排序後的陣列：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

歸併排序可以看作是先遞迴地將待排序陣列切割成多個小塊（每個小塊只有一個元素），然後再逐步合併這些小塊，最終得到完全有序的結果。

歸併排序具有穩定性和時間複雜度為 O(nlogn)的優點，但它需要額外的空間來儲存臨時陣列。在實際應用中，歸併排序常用於對連結串列和外部排序等場景

基數排序

基數排序是一種非比較的排序演演算法，它根據元素的位數進行排序。基數排序的基本思想是將待排序的元素按照個位、十位、百位等位數進行分組，然後依次對每個位數進行穩定的排序。通過多次按位元排序，最終得到完全有序的結果。它是通過鍵值的各個位的值，將要排序的元素分配至某些「桶」中，達到排序的作用，是桶排序的擴充套件。時間複雜度為 O(d * (n + k))，其中 k 表示每個桶的平均大小，元素個數（n）、元素的位數（d），是經典的空間換時間的方式，佔用記憶體很大，當對海量資料排序時容易造成 OOM

以下是基數排序的演演算法步驟：

1. 找到陣列中最大值，並確定最大值的位數。

2. 建立桶陣列和桶計數陣列。桶陣列用於存放待排序元素，桶計數陣列用於記錄每個桶中元素的個數。

3. 從個位開始，按照當前位上的數位將元素分配到對應的桶中。

4. 將每個桶中的元素按順序收集到原始陣列中。

5. 重複步驟 3 和 4，直到遍歷完所有位數。

6. 完成排序後，原始陣列即為有序結果。

程式碼範例:

public class RadixSort {

    public static void radixSort(int[] arr) {

        // 找到陣列中位數最大的數,假設第一個就是最大的
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        // 得到最大位數
        int maxLength = (max + "").length();

        // 定義一個二維陣列表示桶，10個桶表示位數（0123456789）
        int[][] bucket = new int[10][arr.length];

        //記錄桶裡面存了多少個資料，定義一個陣列表示個數
        int[] bucketElementCounts = new int[10];


        for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {
            // 對每個位數的資料進行排序，第一次個位，2次百位，以此類推
            for (int j = 0; j < arr.length; j++) {
                // 取出每個元素對應位的值
                int digitOfElement = arr[j] / n % 10;
                // 放入到對應的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }
            // 按照桶的順序進行排序 一維陣列的下標依次取出資料，放入原來陣列
            int index = 0;
            // 遍歷每一個桶，放入原來的陣列
            for (int k = 0; k < bucketElementCounts.length; k++) {
                // 如果桶中有資料，放入到原陣列
                if (bucketElementCounts[k] != 0){
                    // 迴圈該桶即第k個桶(即第k個一維陣列), 放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                // 每一輪清空桶
                bucketElementCounts[k] = 0;
            }

        }

    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

        System.out.println("原始陣列：" + Arrays.toString(arr));

        radixSort(arr);

        System.out.println("排序後陣列：" + Arrays.toString(arr));
    }

}

堆排序

堆排序是利用堆這個資料結構實現的，堆本質是一個完全二元樹（Complete Binary Tree）：除了最後一層外，其他層的節點都是滿的，並且最後一層的節點都儘可能地靠左排列。

堆分為兩種型別：

最大堆：任何一個父節點的值，都大於或等於左、右孩子節點的值。

最小堆：任何一個父節點的值，都小於或等於它左右孩子節點的值。

二元堆積的根節點叫作堆頂，最大堆和最小堆的特點決定了: 最大堆的堆頂是整個堆中的最大元素最小堆的堆頂是整個堆中的最小元素。

我們還需要明確一點:二元堆積雖然是一個完全二元樹，但它的儲存方式並不是鏈式儲存，而是順序儲存。換句話說，二元堆積的所有節點都儲存在陣列中。

左孩子下標就是 2xparent+1

右孩子下標就是 2xparent+2

堆的最後一個非葉子節點的計算公式為 (n/2) - 1，其中 n 是堆中元素的總數。

理解以上就可以實現一個堆排序，步驟如下：

1.構造初始堆。將給定無序序列構造成一個大頂堆（一般升序採用大頂堆，降序採用小頂堆)

2.排序。將最大堆中的根節點（最大值）與陣列中未排序部分的最後一個元素交換位置，將最大元素"沉"到陣列末端;重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與當前末尾元素，反覆執行調整+交換步驟，直到整個序列有序

程式碼實現：

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        // 構建最大堆
        buildMaxHeap(arr, n);
        // 逐步取出最大元素並調整堆
        for (int i = n - 1; i > 0; i--) {
            // 將當前根節點（最大值）與末尾元素交換
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // 調整堆
            heapify(arr, i, 0);
        }
    }
    private static void buildMaxHeap(int[] arr, int n) {
        // 從最後一個非葉子節點開始，依次向前調整堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }
    private static void heapify(int[] arr, int n, int root) {
        while (true) {
            int largest = root; // 初始化根節點為最大值
            int leftChild = 2 * root + 1;
            int rightChild = 2 * root + 2;
            // 如果左子節點比根節點大，則更新最大值索引
            if (leftChild < n && arr[leftChild] > arr[largest]) {
                largest = leftChild;
            }
            // 如果右子節點比當前最大值大，則更新最大值索引
            if (rightChild < n && arr[rightChild] > arr[largest]) {
                largest = rightChild;
            }
            // 如果最大值索引不是根節點，則交換根節點和最大值節點，並繼續迴圈調整堆
            if (largest != root) {
                int temp = arr[root];
                arr[root] = arr[largest];
                arr[largest] = temp;
                root = largest;
            } else {
                break;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {9, 4, 2, 7, 1, 5, 8, 3, 6};
//        int[] arr = {4,6,8,5,9};
        heapSort(arr);
        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}