| 排序办法 | 工夫复杂度（均匀） | 工夫复杂度（最坏） | 工夫复杂度（最好） | 空间复杂度 | 稳定性 | 复杂性 |
|---|---|---|---|---|---|---|
| 插入排序 | 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;
}
}
}
}…. 待欠缺，最终会把所有罕用排序都放进来