1 基本原理
希尔排序是一种递减增量插入排序算法。普通的插入排序的是以1为间隔进行排序，希尔排序是在其上做的优化，比如取一间隔序列为1，4，9 ，首先以9为间隔排序，再次以4为间隔排序，最后以1为间隔排序，就是普通的插入排序。
2 实现
public static void ShellSort(int[] a){
int n = a.length;
int h = 1;
while(h < n/3){
h = 3*h + 1;
}
while(h >= 1){
for(int i = h; i < n; i++){
for(int j = i; j >= h && SortUtil.less(a,j,j-h);j -= h){
SortUtil.swap(a,j,j-h);
}
}
h /= 3;
}
}
3 算法分析
时间复杂度不好分析，空间复杂度是O(1)，不稳定算法
网友评论