希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的[时间复杂度会比o(n^2)好一些。
代码如下
/**
*
* 希尔排序
*
* 希尔排序思想：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，
* 待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序
* 希尔排序时间复杂度为O(n^3/2)
*
*/
public class ShellSort {
/**
* 外层排序算法
* @param arr 要排序的数组
* @param dl 增量数组，每次按照增量分割子序列进行排序，增量数组中最后一个必须为1
*/
static void shellSort(int arr[],int dl[]){
for(int i = 0;i<dl.length;i++){
shellInsert(arr,dl[i]);
System.out.println("第"+(i+1)+"趟排序结果:");
display(arr);
}
}
/**
* 以d为增量对数组arr分割成子序列，并对各子序列进行直接插入排序，如果把d换为1则是直接插入排序算法
* @param arr 要排序的数组
* @param d 增量
*/
static void shellInsert(int arr[],int d){
//由于数组是从0下标开始，所以0+d为增量后的第一个元素
for(int i = d;i<arr.length;i++){ //下面就是插入排序的逻辑了，不过每次不是与相邻的数进行比较，而是与相隔d个数进行比较
if(arr[i]<arr[i-d]){
int temp = arr[i];
int j = i-d;
for(;j>=0 && temp<arr[j];j -= d){
arr[j+d] = arr[j];
}
arr[j+d] = temp;
}
}
}
public static void display(int[] arr){
for(int i = 0;i<arr.length;i++) {
System.out.print(arr[i]+",");
}
System.out.println();
}
public static void main(String[] args) {
int arr[] = {49,38,65,97,76,13,27,49,55,4};
int dl[] = {5,3,1};
shellSort(arr,dl);
System.out.println("排序结果为：");
display(arr);
}
}
