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 + " ");
        }
    }
}