package com.rao.sort; import java.util.Arrays; /**
* @author Srao
* @className ShellSort
* @date 2019/12/4 13:05
* @package com.rao.sort
* @Description 希尔排序
*/
public class ShellSort {
/**
* 希尔排序
* @param arr：要排序的数组
*/
public static void shellSort(int[] arr){
int n = arr.length;
//把数组进行分组，组数为数组的长度除以2， 4， 8... 直到只能分成一组
for (int h = n/; h > ; h = h/){
for (int i = h; i < n; i++){
insertI(arr, h, i);
}
}
} /**
* 插入排序
* @param arr：要排序的数组
* @param h：分组之间的间隔
* @param i：要进行插入排序的元素的下标
*/
public static void insertI(int[] arr, int h, int i){
//先把要进行插入的元素保存起来
int temp = arr[i];
int k;
//因为每一组的元素之间是间隔着其它的元素，
//所以同一组元素的下标是... i-2*h, i-h, i, i+h, i+2*h ...
//如果要插入的元素前面的数比它大的话，就把那个元素向后移动一位
for (k = i-h; k>= && temp<arr[k]; k = k-h){
arr[k+h] = arr[k];
}
//把元素插入
arr[k+h] = temp;
} public static void main(String[] args) {
int[] arr = new int[]{,,,,,,,};
System.out.println(Arrays.toString(arr));
shellSort(arr);
System.out.println(Arrays.toString(arr)); }
}
希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要 n - 1 次移动。也就是说，原数组的一个元素如果距离它正确的位置很远的话，则需要与相邻元素交换很多次才能到达正确的位置，这样是相对比较花时间了。
希尔排序就是为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序。
希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。
