本文提供一個完整的 MySort 工具類，涵蓋直接插入排序、冒泡排序、快速排序、簡單選擇排序、希爾排序五種經典算法，並附帶統一測試入口與打印方法，便於對比學習。
public class MySort {
public static void main(String[] args) {
int[] array = {45,32,54,12,43,65,11,3,43,6,33,90,44,1,178};
MySort sort = new MySort();
// 依次調用各排序方法並打印結果
sort.insertSort(array.clone()); // 插入排序
sort.bubbleSort(array.clone()); // 冒泡排序
sort.qsort(array.clone()); // 快速排序
sort.shellSort(array.clone()); // 希爾排序
sort.selectSort(array.clone()); // 選擇排序
}
// 五大排序方法實現...
public void printArray(int[] array) { ... }
}
| 算法 | 核心思想 | 平均時間複雜度 | 穩定性 |
|---|---|---|---|
| 直接插入排序 | 將第 n 個元素插入前 n-1 個有序序列 | O(n²) | 穩定 |
| 冒泡排序 | 相鄰元素比較交換，大元素沉底、小元素冒頂 | O(n²) | 穩定 |
| 快速排序 | 分治法：選基準值，左小右大，遞歸排序子序列 | O(n log n) | 不穩定 |
| 簡單選擇排序 | 每輪選出最小元素與首位交換 | O(n²) | 不穩定 |
| 希爾排序 | 分組插入排序，增量逐漸縮小至 1 | O(n^1.3~n²) | 不穩定 |
public void qsort(int[] array) {
if (array.length > 1) _qsort(array, 0, array.length - 1);
}
private void _qsort(int[] array, int low, int high) {
if (low < high) {
int middle = getMiddle(array, low, high);
_qsort(array, low, middle - 1);
_qsort(array, middle + 1, high);
}
}
private int getMiddle(int[] array, int low, int high) {
int tmp = array[low];
while (low < high) {
while (low < high && array[high] >= tmp) high--;
array[low] = array[high];
while (low < high && array[low] <= tmp) low++;
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public void shellSort(int[] array) {
double d1 = array.length;
while (true) {
d1 = Math.ceil(d1 / 2);
int d = (int) d1;
for (int x = 0; x < d; x++) {
for (int i = x + d; i < array.length; i += d) {
int j = i - d;
int temp = array[i];
for (; j >= 0 && temp < array[j]; j -= d) {
array[j + d] = array[j];
}
array[j + d] = temp;
}
}
if (d == 1) break;
}
}
初學者可通過調試觀察各輪排序後的數組變化，理解「有序區擴展」「分治遞歸」「增量分組」等核心思想。實際工程中，除教學與極小數據量場景外，優先使用 Arrays.sort()（雙軸快排）或 Collections.sort()（TimSort）。
