```希尔排序 Shell Sort 是插入排序的一种

3,2,1,9,4,8,7,5,6

gap=4
3 2 1 5 4 8 7 9 6
gap=2
1 2 3 5 4 8 6 9 7
gap=1
1 2 3 4 5 6 7 8 9

public class ShellSort {
public static void main(String[] args) throws Exception {
int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 };
shellSort(arr);
}

private static void shellSort(int[] arr) {
final int N = arr.length;
int gap = N / 2;
int i, j;
while (gap > 0) {
for (i = 0; i < gap; i++) {
for (j = i + gap; j < N; j += gap) {
for (int k = j - gap; k >= i; k -= gap) {
if (arr[k] > arr[gap + k]) {
swap(arr, k, gap + k);
}

}
}
}
// for debug
System.out.println("gap=" + gap);
printArr(arr);
gap /= 2;
}
}

private static void printArr(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
sb.append(arr[i]).append(" ");
}
System.out.println(sb.toString());
}

private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

https://gitee.com/dyyx/hellocode/blob/master/src/algo/sort/ShellSort.java

冒泡选择和插入排序比较
```

Java assert