希尔排序算法介绍：
希尔排序是希尔于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
写入排序法的基本思想：
希尔排序十八记录按下标的一定增量分组，对每组使用直接插入算法排序：随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰号被分作一组，算法便终止。
希尔排序算法示意图：
方法一【交换法】：
1 import java.util.Arrays;
2
3 //希尔排序算法
4 public class ShellSort {
5
6 public static void main(String[] args) {
7 int[] arr = {8,9,1,7,2,3,5,4,6,0};
8 shellSort(arr);
9 loopShellSort(arr);
10 }
11
12 public static void loopShellSort(int[] arr) {
13 int tmp = 0;
14 int count = 0;
15 for(int gap = arr.length/2; gap > 0; gap /= 2) {
16 for(int i = gap; i < arr.length; i++) {
17 for(int j = i - gap; j >= 0; j -= gap) {
18 if (arr[j] > arr[j+gap]) {
19 tmp = arr[j];
20 arr[j] = arr[j+gap];
21 arr[j+gap] = tmp;
22 }
23 }
24 }
25 System.out.println("第" + (++count) + "轮：" + Arrays.toString(arr));
26 }
27 }
28
29 public static void shellSort(int[] arr) {
30 int tmp = 0;
31 for(int i = 5; i < arr.length; i++) {
32 for(int j = i-5; j >= 0; j -= 5) { //步长为5【即相隔5个为一组】
33 if (arr[j] > arr[j+5]) {
34 tmp = arr[j];
35 arr[j] = arr[j+5];
36 arr[j+5] = tmp;
37 }
38 }
39 }
40 System.out.println("第1轮排序后：" + Arrays.toString(arr));
41
42 for(int i = 2; i < arr.length; i++) {
43 for(int j = i-2; j >= 0; j -= 2) { //步长为2【即相隔2个为一组】
44 if (arr[j] > arr[j+2]) {
45 tmp = arr[j];
46 arr[j] = arr[j+2];
47 arr[j+2] = tmp;
48 }
49 }
50 }
51 System.out.println("第2轮排序后：" + Arrays.toString(arr));
52
53 for(int i = 1; i < arr.length; i++) {
54 for(int j = i-1; j >= 0; j -= 1) { //步长为1【即相隔1个为一组】
55 if (arr[j] > arr[j+1]) {
56 tmp = arr[j];
57 arr[j] = arr[j+1];
58 arr[j+1] = tmp;
59 }
60 }
61 }
62 System.out.println("第3轮排序后：" + Arrays.toString(arr));
63 }
64
65 }
shellSort方法是演变希尔排序算法的过程，而loopShellSort方法是总结其规律，然后用循环实现，再次展示示例程序执行结果：
优化：使用移位法：
