| 排序办法 | 工夫复杂度（均匀） | 工夫复杂度（最坏） | 工夫复杂度（最好） | 空间复杂度 | 稳定性 | 复杂性 |
|---|---|---|---|---|---|---|
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳固 | 简略 |
| 希尔排序 | O(nlogn) | O(n^2) | O(n^1.3) | O(1) | 不稳固 | 较简单 |
一、插入排序
public static void sort(int[] arr) { for (int i = 1; i < arr.length; i++) { int tmp = arr[i]; int j; for (j = i - 1; j >= 0 && tmp < arr[j]; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = tmp; }}二、希尔排序（放大增量排序）
public static void sort(int[] arr) { for (int gap = arr.length / 2; gap > 0; gap = gap / 2) { for (int i = 0; i < gap; i++) { for (int j = i + gap; j < arr.length; j += gap) { int tmp = arr[j]; int k; for (k = j - gap; k >= 0 && tmp < arr[k]; k -= gap) { arr[k + gap] = arr[k]; } arr[k + gap] = tmp; } } }}....待欠缺，最终会把所有罕用排序都放进来