以下是典型的排序算法分類及對應的 Java 實現，包含時間復雜度、穩定性說明和核心代碼示例：

---

一、比較類排序（通過元素比較）

1. 交換排序

① 冒泡排序
時間復雜度：O(n2)（優化后最優O(n)）
穩定性：穩定

public static void bubbleSort(int[] arr) {boolean swapped;for (int i = 0; i < arr.length - 1; i++) {swapped = false;for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}if (!swapped) break; // 提前終止優化}
}

② 快速排序
時間復雜度：平均 O(n log n)，最差 O(n2)
穩定性：不穩定

public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}
}private 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;
}

---

2. 插入排序

① 直接插入排序
時間復雜度：O(n2)（最優O(n)）
穩定性：穩定

public static void insertionSort(int[] arr) {for (int i = 1; i < arr.length; 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;}
}

---

3. 選擇排序

① 簡單選擇排序
時間復雜度：O(n2)
穩定性：不穩定

public static void selectionSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {int minIdx = i;for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIdx]) {minIdx = j;}}int temp = arr[minIdx];arr[minIdx] = arr[i];arr[i] = temp;}
}

---

4. 歸并排序

時間復雜度：O(n log n)
穩定性：穩定

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);}
}private static void merge(int[] arr, int left, int mid, int right) {int[] temp = new int[right - left + 1];int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];}while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];System.arraycopy(temp, 0, arr, left, temp.length);
}

---

5. 堆排序

時間復雜度：O(n log n)
穩定性：不穩定

public static void heapSort(int[] arr) {// 構建最大堆for (int i = arr.length / 2 - 1; i >= 0; i--) {heapify(arr, arr.length, i);}// 逐步提取堆頂元素for (int i = arr.length - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}
}private static void heapify(int[] arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest]) largest = left;if (right < n && arr[right] > arr[largest]) largest = right;if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}
}

---

二、非比較類排序（利用數值特征）

1. 計數排序

時間復雜度：O(n + k)（k 為數據范圍）
穩定性：穩定
適用場景：整數且范圍較小

public static void countingSort(int[] arr) {int max = Arrays.stream(arr).max().getAsInt();int[] count = new int[max + 1];for (int num : arr) count[num]++;int idx = 0;for (int i = 0; i <= max; i++) {while (count[i]-- > 0) {arr[idx++] = i;}}
}

---

2. 基數排序

時間復雜度：O(nk)（k 為最大位數）
穩定性：穩定

public static void radixSort(int[] arr) {int max = Arrays.stream(arr).max().getAsInt();for (int exp = 1; max / exp > 0; exp *= 10) {countSortByDigit(arr, exp);}
}private static void countSortByDigit(int[] arr, int exp) {int[] output = new int[arr.length];int[] count = new int[10];for (int num : arr) count[(num / exp) % 10]++;for (int i = 1; i < 10; i++) count[i] += count[i - 1];for (int i = arr.length - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}System.arraycopy(output, 0, arr, 0, arr.length);
}

---

三、總結與選擇建議

算法	平均時間復雜度	空間復雜度	穩定性	適用場景
冒泡排序	O(n2)	O(1)	穩定	小數據、教學演示
快速排序	O(n log n)	O(log n)	不穩定	通用場景（優化后高效）
歸并排序	O(n log n)	O(n)	穩定	大數據、穩定排序需求
堆排序	O(n log n)	O(1)	不穩定	原地排序、內存敏感場景
計數排序	O(n + k)	O(k)	穩定	整數且數值范圍小
基數排序	O(nk)	O(n + k)	穩定	多位數整數（如身份證號）

實際建議：

• 小規模數據：插入排序或冒泡排序（簡單實現）。
• 通用場景：優先選擇快速排序（需優化基準選擇）。
• 穩定排序需求：歸并排序或基數排序。
• 特定數值特征：計數排序/基數排序效率碾壓比較排序。