希尔排序法基本思想：
把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个记录恰被分成一组，算法便终止
import java.util.Arrays; /** * 希尔排序 */ public class ShellSort { //交换式 public static int[] shellSort(int[] arr){ int length = arr.length; int temp = 0; int count = 0; //gap 为步长,也是组数 for (int gap = length/2; gap >0 ; gap/=2) { //从第一组的第一个开始遍历所有元素。因为内部循环会-gap，也就是从第一组的第一个开始 for (int i = gap; i <length; i++) { //遍历组中所有的元素，步长gap，会从后到前把大的排后面 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)); } System.out.println("第"+(++count)+"轮，步长为"+gap+":="+Arrays.toString(arr)); } return arr; } //交换式优化->位移式 public static int[] shellSort2(int[] arr){ int length = arr.length; int temp = 0; int count = 0; //gap 为步长,也是组数 for (int gap = length/2; gap >0 ; gap/=2) { // for (int i = gap; i <length; i++) { int j = i; temp = arr[j]; if (arr[j]<arr[j-gap]){ //把比temp的都向后移动 while (j-gap>=0&&temp<arr[j-gap]){ arr[j]=arr[j-gap]; j-=gap; } //temp插入 arr[j] = temp; } System.out.println(Arrays.toString(arr)); } System.out.println("第"+(++count)+"轮，步长为"+gap+":="+Arrays.toString(arr)); } return arr; } public static void main(String[] args){ shellSort(new int[]{8,1,7,2,3,5,4,6,0}); //[3, 1, 7, 2, 8, 5, 4, 6, 0] //[3, 1, 7, 2, 8, 5, 4, 6, 0] //[3, 1, 4, 2, 8, 5, 7, 6, 0] //[3, 1, 4, 2, 8, 5, 7, 6, 0] //[0, 1, 4, 2, 3, 5, 7, 6, 8] //第1轮，步长为4:=[0, 1, 4, 2, 3, 5, 7, 6, 8] //[0, 1, 4, 2, 3, 5, 7, 6, 8] //[0, 1, 4, 2, 3, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //第2轮，步长为2:=[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 6, 7, 8] //[0, 1, 2, 3, 4, 5, 6, 7, 8] //第3轮，步长为1:=[0, 1, 2, 3, 4, 5, 6, 7, 8] shellSort2(new int[]{8,1,7,2,3,5,4,6,0}); //[3, 1, 7, 2, 8, 5, 4, 6, 0] //[3, 1, 7, 2, 8, 5, 4, 6, 0] //[3, 1, 4, 2, 8, 5, 7, 6, 0] //[3, 1, 4, 2, 8, 5, 7, 6, 0] //[0, 1, 4, 2, 3, 5, 7, 6, 8] //第1轮，步长为4:=[0, 1, 4, 2, 3, 5, 7, 6, 8] //[0, 1, 4, 2, 3, 5, 7, 6, 8] //[0, 1, 4, 2, 3, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //第2轮，步长为2:=[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 3, 2, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 7, 6, 8] //[0, 1, 2, 3, 4, 5, 6, 7, 8] //[0, 1, 2, 3, 4, 5, 6, 7, 8] //第3轮，步长为1:=[0, 1, 2, 3, 4, 5, 6, 7, 8] } }