希尔排序（Shell‘s Sort）属于不稳定排序，时间复杂度为O(n^s) 1<s<2，是插入排序的一种更高效的改进版本，也称为缩小增量排序
思路：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
过程：数组长度除2分组，向下取整，对分好组后的数据进行插入排序，然后对已经分好的数组接着除2，直到结束
在进行数据分组交换的时候有两种方法：交换法和移动法，移动法相对来说比较快速，两个方法的都写了一下
import javax.sound.midi.Soundbank; import java.util.Arrays; public class ShellSort { public static void main(String[] args) { int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; shellSort2(arr); } //交换式 public static void shellSort(int[] arr) { int temp = 0; for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { for (int j = i - gap; j >= 0; j -= gap) { if (arr[j] > arr[j + gap]) { temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } } System.out.println(Arrays.toString(arr)); } //移动式 public static void shellSort2(int[] arr) { for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { int j = i; int temp = arr[i]; if (arr[j] < arr[j - gap]) { while (j - gap >= 0 && temp < arr[j - gap]) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } } System.out.println(Arrays.toString(arr)); } }
原文：https://www.cnblogs.com/bingbug/p/12118732.html