Java 中的排序算法詳解

一、冒泡排序（Bubble Sort）

原理?

二、選擇排序（Selection Sort）

原理?

三、插入排序（Insertion Sort）

原理?

四、快速排序（Quick Sort）

原理?

五、歸并排序（Merge Sort）

原理?

六、希爾排序（Shell Sort）

原理?

七、總結

作為一名 Java 初學者，掌握排序算法是編程路上的重要一步。排序算法不僅能幫助我們更好地理解數據處理邏輯，還能在實際開發中解決各種問題。

一、冒泡排序（Bubble Sort）

泡排序是最基礎的排序算法之一，它的核心思想是通過重復遍歷要排序的數組，每次比較相鄰的兩個元素，如果它們的順序錯誤就把它們交換過來。

原理?

就像水中的氣泡會逐漸上浮一樣，越大的元素會經由交換慢慢 “浮” 到數組的末端。具體來說，每一輪遍歷都會將當前未排序部分中最大的元素移動到正確的位置。

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 = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println("排序后的數組：");for (int num : arr) {System.out.print(num + " ");}}
}

?排序后的數組：
?11 12 22 25 34 64 90?

優缺點?：

優點：實現簡單，易于理解，是入門排序算法的好選擇。?

缺點：效率較低，時間復雜度為 O (n2)，在處理大規模數據時性能不佳。

二、選擇排序（Selection Sort）

選擇排序的思路相對直觀，它每次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

原理?

首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小元素，放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

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, 25, 12, 22, 11};selectionSort(arr);System.out.println("排序后的數組：");for (int num : arr) {System.out.print(num + " ");}}
}

排序后的數組：
11 12 22 25 64?

優缺點?：

優點：實現簡單，相較于冒泡排序，交換次數更少。?

缺點：時間復雜度仍為 O (n2)，不適合處理大量數據。

三、插入排序（Insertion Sort）

插入排序的工作方式類似于我們整理手中的撲克牌，它將數組分為已排序和未排序兩部分，每次從為排序部分中取出一個元素，插入到已排序部分的正確位置。

原理?

從第一個元素開始，該元素可以認為已經被排序；取出下一個元素，在已經排序的元素序列中從后向前掃描；如果該元素（已排序）大于新元素，將該元素移到下一位置；重復上一步驟，直到找到已排序的元素小于或者等于新元素的位置；將新元素插入到該位置后；重復以上步驟。

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;// 將大于key的元素向后移動一位while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6};insertionSort(arr);System.out.println("排序后的數組：");for (int num : arr) {System.out.print(num + " ");}}
}

?排序后的數組：
5 6 11 12 13?

優缺點?：

優點：對于近乎有序的數組，插入排序的效率很高，時間復雜度可接近 O (n)；實現也較為簡單。?

缺點：在處理完全無序的大規模數據時，時間復雜度仍為 O (n2)。

四、快速排序（Quick Sort）

快速排序是一種高效的排序算法，它采用了分治法的思想，通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，然后分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。

原理?

選擇一個元素作為 “基準”（pivot），通常選擇數組的第一個元素、最后一個元素或中間元素。然后將所有比基準值小的元素放在基準前面，所有比基準值大的元素放在基準后面，這個過程稱為分區（partition）操作。接著，對基準前后的兩個子數組分別重復上述過程，直到子數組的長度為 1 或 0。

public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {// 分區操作，得到基準元素的正確位置int pi = partition(arr, low, high);// 遞歸排序基準元素左邊和右邊的子數組quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}private static int partition(int[] arr, int low, int high) {// 選擇最右邊的元素作為基準int pivot = arr[high];// i表示小于基準元素的區域的邊界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 = {10, 7, 8, 9, 1, 5};int n = arr.length;quickSort(arr, 0, n - 1);System.out.println("排序后的數組：");for (int num : arr) {System.out.print(num + " ");}}
}

排序后的數組：
1 5 7 8 9 10?

優缺點?：

優點：平均時間復雜度為 O (n log n)，效率高，在實際應用中廣泛使用。?

缺點：在最壞情況下（如數組已經有序），時間復雜度會退化為 O (n2)；不穩定，可能會改變相等元素的相對順序。

五、歸并排序（Merge Sort）

歸并排序同樣基于分治法，它的核心是將兩個或兩個以上的有序表合并成一個新的有序表。?

原理?

將待排序數組不斷二分，直到每個子數組只包含一個元素（此時子數組自然有序）。然后，將這些有序的子數組兩兩合并，每次合并都得到一個更大的有序數組，重復這個過程，直到最終得到一個完整的有序數組。

public class MergeSort {// 合并兩個有序子數組public static void merge(int[] arr, int left, int mid, int right) {// 計算兩個子數組的長度int n1 = mid - left + 1;int n2 = right - mid;// 創建臨時數組int[] L = new int[n1];int[] R = new int[n2];// 將數據復制到臨時數組for (int i = 0; i < n1; ++i) {L[i] = arr[left + i];}for (int j = 0; j < n2; ++j) {R[j] = arr[mid + 1 + j];}// 合并臨時數組int i = 0, j = 0;int k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 復制剩余元素while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}}// 歸并排序主方法public static void mergeSort(int[] arr, int left, int right) {if (left < right) {// 找到中間點int mid = left + (right - left) / 2;// 遞歸排序左右兩部分mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并已排序的兩部分merge(arr, left, mid, right);}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6, 7};int n = arr.length;mergeSort(arr, 0, n - 1);System.out.println("排序后的數組：");for (int num : arr) {System.out.print(num + " ");}}
}

排序后的數組：
5 6 7 11 12 13?

優缺點?

優點：時間復雜度穩定為 O (n log n)，不受輸入數據的影響；是穩定的排序算法。?

缺點：需要額外的存儲空間，空間復雜度為 O (n)。

六、希爾排序（Shell Sort）

希爾排序是插入排序的一種改進版本，它通過將數組按照一定的間隔分組，對每組進行插入排序，然后逐漸縮小間隔，直到間隔為 1，此時進行最后一次插入排序，使數組完全有序。?

原理?

先確定一個增量序列，增量序列可以有多種選擇，常見的有初始增量為數組長度的一半，之后每次減半，直到增量為 1。對于每個增量，將數組中所有距離為該增量的元素組成一個子數組，對每個子數組進行插入排序。隨著增量逐漸減小，子數組的長度逐漸增大，當增量為 1 時，整個數組就是一個子數組，此時進行一次插入排序，數組就會變得有序。

public class ShellSort {public static void shellSort(int[] arr) {int n = arr.length;// 初始增量為數組長度的一半，之后每次減半for (int gap = n / 2; gap > 0; gap /= 2) {// 對每個子數組進行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;// 移動同組中比temp大的元素for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}}public static void main(String[] args) {int[] arr = {12, 34, 54, 2, 3};shellSort(arr);System.out.println("排序后的數組：");for (int num : arr) {System.out.print(num + " ");}}
}