本文整理了插入、選擇、交換、歸併、堆、希爾等六類排序的標準實現，並從時間/空間複雜度、穩定性維度進行對比，幫助選型。
package test;
public class SortAlgorithms {
/** 直接插入排序 - O(n²), 穩定 */
public void insertSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int temp = a[i], j = i;
while (j > 0 && a[j - 1] > temp) {
a[j] = a[j - 1];
j--;
}
a[j] = temp;
}
}
/** 折半插入排序 - 比較次數減少，移動次數不變 */
public void binInsertSort(int[] a, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int temp = a[i];
int lo = low, hi = i - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
if (temp < a[mid]) hi = mid - 1;
else lo = mid + 1;
}
for (int j = i - 1; j >= lo; j--) a[j + 1] = a[j];
a[lo] = temp;
}
}
/** 希爾排序 - 縮小增量排序 */
public void shellSort(int[] a, int[] gaps) {
for (int gap : gaps) {
for (int i = gap; i < a.length; i++) {
int temp = a[i], j = i;
while (j >= gap && a[j - gap] > temp) {
a[j] = a[j - gap];
j -= gap;
}
a[j] = temp;
}
}
}
/** 簡單選擇排序 - O(n²), 不穩定 */
public void selectSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++)
if (a[j] < a[min]) min = j;
if (min != i) { int t = a[i]; a[i] = a[min]; a[min] = t; }
}
}
/** 堆排序 - O(n log n), 不穩定, 原地 */
public void heapSort(int[] a) {
int n = a.length;
// 建堆 (從最後一個非葉子節點開始)
for (int i = n / 2 - 1; i >= 0; i--) heapify(a, n, i);
// 逐個提取
for (int i = n - 1; i > 0; i--) {
swap(a, 0, i);
heapify(a, i, 0);
}
}
private void heapify(int[] a, int n, int i) {
int largest = i;
int l = 2 * i + 1, r = 2 * i + 2;
if (l < n && a[l] > a[largest]) largest = l;
if (r < n && a[r] > a[largest]) largest = r;
if (largest != i) { swap(a, i, largest); heapify(a, n, largest); }
}
/** 歸併排序 - O(n log n), 穩定, 需 O(n) 空間 */
public void mergeSort(int[] a) {
int[] temp = new int[a.length];
mergeSort(a, 0, a.length - 1, temp);
}
private void mergeSort(int[] a, int l, int r, int[] temp) {
if (l >= r) return;
int m = (l + r) >>> 1;
mergeSort(a, l, m, temp);
mergeSort(a, m + 1, r, temp);
merge(a, l, m, r, temp);
}
private void merge(int[] a, int l, int m, int r, int[] temp) {
int i = l, j = m + 1, k = l;
while (i <= m && j <= r) temp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= m) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
System.arraycopy(temp, l, a, l, r - l + 1);
}
/** 快速排序 - 平均 O(n log n), 最壞 O(n²), 不穩定 */
public void quickSort(int[] a) {
quickSort(a, 0, a.length - 1);
}
private void quickSort(int[] a, int l, int r) {
if (l >= r) return;
int p = partition(a, l, r);
quickSort(a, l, p - 1);
quickSort(a, p + 1, r);
}
private int partition(int[] a, int l, int r) {
int pivot = a[r];
int i = l - 1;
for (int j = l; j < r; j++)
if (a[j] <= pivot) swap(a, ++i, j);
swap(a, i + 1, r);
return i + 1;
}
private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}| 算法 | 平均時間 | 最壞時間 | 最好時間 | 空間 | 穩定 | 備註 |
|---|---|---|---|---|---|---|
| 插入排序 | O(n²) | O(n²) | O(n) | O(1) | ✅ | 小數據/近乎有序極快 |
| 折半插入 | O(n²) | O(n²) | O(n) | O(1) | ✅ | 減少比較，移動不變 |
| 希爾排序 | O(n^1.3~n²) | O(n²) | O(n) | O(1) | ❌ | 增量序列影響大 |
| 選擇排序 | O(n²) | O(n²) | O(n²) | O(1) | ❌ | 交換次數最少 O(n) |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | 原地、保證性能 |
| 歸併排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | 穩定、外排序基礎 |
| 快速排序 | O(n log n) | O(n²) | O(n log n) | O(log n) | ❌ | 實際最快、隨機化避免最壞 |
| 冒泡排序 | O(n²) | O(n²) | O(n) | O(1) | ✅ | 教學用、優化後近乎有序快 |
Arrays.sort() (雙軸快排/歸併)Arrays.parallelSort()Arrays.sort() → 雙軸快速排序 (Dual-Pivot Quicksort)Arrays.sort() / Collections.sort() → TimSort (歸併+插入混合)，穩定Arrays.parallelSort() → 多線程歸併/快速混合沒有「最好」的排序，只有「最合適」的排序。理解各算法的時空權衡、穩定性、數據特徵敏感度，結合實際數據規模、有序度、內存限制、穩定性要求進行選型。生產代碼優先使用 JDK 內置 Arrays.sort() / parallelSort()，特殊場景再手工實現優化。
