/**
* 希尔排序思想：先将整个待排记录序列分割成若干子序列分别进行直接插入排序，
* 待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序
* 希尔排序时间复杂度为O(n^3/2)
*
*/
public class ShellSort {
/**
* 以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++){
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;
}
}
}
/**
* 外层排序算法
* @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)+"趟排序结果:");
for(int j = 0;j<arr.length;j++)
System.out.println(arr[j]);
}
}
//测试.....
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("排序结果为：");
for(int i = 0;i<arr.length;i++)
System.out.println(arr[i]);
}
}
