简介
希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
前面学习插入排序的时候，我们会发现一个很不友好的事儿，如果已排序的分组元素为{2,5,7,9,10}，未排序的分组 元素为{1,8}，那么下一个待插入元素为1，我们需要拿着1从后往前，依次和10,9,7,5,2进行交换位置，才能完成真 正的插入，每次交换只能和相邻的元素交换位置。那如果我们要提高效率，直观的想法就是一次交换，能把1放到更前面的位置，比如一次交换就能把1插到2和5之间，这样一次交换1就向前走了5个位置，可以减少交换的次数， 这样的需求如何实现呢？接下来我们来看看希尔排序的原理。
排序原理：
1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
2.对分好组的每一组数据完成插入排序；
3.减小增长量，最小减为1，重复第二步操作。
增长量h的确定：增长量h的值每一固定的规则，我们这里采用以下规则：
int h=1
while(h<5){
h=2h+1;
}
//循环结束后我们就可以确定h的最大值；
h的减小规则为：
h=h/2
java代码实现：
/**
* 希尔排序
* @author wen.jie
* @date 2021/8/5 9:26
*/
public class Shell {
/**
* 排序
* @author wen.jie
* @date 2021/8/4 17:28
*/
public static void sort(Comparable<?>[] a) {
//1.根据数组a的长度确定增长量
int h = 1;
while (h < a.length/2) {
h = 2 * h + 1;
}
//2.希尔排序
while (h >= 1){
//找到待插入的元素
for (int i = h; i < a.length; i++) {
//把待插入的元素插入到有序数列中
for(int j = i; j >= h; j -= h){
if(greater(a[j-h], a[j])){
exchange(a, j-h, j);
} else break;
}
}
h = h/2;
}
}
/**
* 比较
* @author wen.jie
* @date 2021/8/4 17:18
*/
private static boolean greater(Comparable v, Comparable w) {
return v.compareTo(w) > 0;
}
/**
* 交换
* @author wen.jie
* @date 2021/8/4 17:27
*/
private static void exchange(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
时间复杂度
希尔排序的分析是一个复杂问题，因为他的时间按是所取增量序列的函数（跟增长量h有关），这涉及到一些数学上尚未解决的问题。因此，到目前为止尚未有人取得一种最好的增量序列，但大量的研究已经得出一些局部的结论。
具体时间复杂度推导看参考：https://zhuanlan.zhihu.com/p/73726253