- 算法可视化：连接
- 时间复杂度，平均：\(O(n^{1.5})\)，最好：\(O(n)\)，最坏：\(O(n^2)\)
- 空间复杂度，\(O(1)\)
- 是否稳定：不稳定
- 图片来源：https://www.cnblogs.com/chengxiao/p/6104371.html
算法思想
- 希尔排序是把记录按下标的一定增量分组，对每组采用插入排序算法
- 增量每次递减一半，当增量为 1 的时候整个数组恰好为一组，算法终止
- 默认增量采用 array.length/2
算法过程
实现
public void sort(int[] array) {
for (int gap = array.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
int j = i;
while (j - gap >= 0 && array[j] < array[j - gap]) {
swap(array, j, j - gap);
j -= gap;
}
}
}
}
public void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}