别名：缩小增量排序 实质：插入排序 理论时间复杂度：O(n^2) 空间复杂度：O(1)
代码实现
public class Demo { public static void main(String[] args) { int arr[] = {5, 3, 9, 7, 6, 1, 2, 4, 8, 0}; shellSort(arr); System.out.println(Arrays.toString(arr)); } public static void shellSort(int[] arr){ int gap = arr.length; while (gap > 1) { gap /= 2; for (int i=0; i < gap; i++) { for (int j=i+gap; j<arr.length; j+=gap){ int tmp = arr[j]; int k; for(k = j-gap; k>=0 && arr[k]>tmp; k = k-gap){ arr[k+gap] = arr[k]; } arr[k + gap] = tmp; } } } } }排序过程
[5, 3, 9, 7, 6, 1, 2, 4, 8, 0] [1, 3, 9, 7, 6, 5, 2, 4, 8, 0] [1, 2, 9, 7, 6, 5, 3, 4, 8, 0] [1, 2, 4, 7, 6, 5, 3, 9, 8, 0] [1, 2, 4, 7, 6, 5, 3, 9, 8, 0] [1, 2, 4, 7, 0, 5, 3, 9, 8, 6] [1, 2, 4, 7, 0, 5, 3, 9, 8, 6] [0, 2, 1, 7, 4, 5, 3, 9, 8, 6] [0, 2, 1, 7, 3, 5, 4, 9, 8, 6] [0, 2, 1, 7, 3, 5, 4, 9, 8, 6] [0, 2, 1, 7, 3, 5, 4, 9, 8, 6] [0, 2, 1, 5, 3, 7, 4, 9, 8, 6] [0, 2, 1, 5, 3, 7, 4, 9, 8, 6] [0, 2, 1, 5, 3, 6, 4, 7, 8, 9] [0, 2, 1, 5, 3, 6, 4, 7, 8, 9] [0, 1, 2, 5, 3, 6, 4, 7, 8, 9] [0, 1, 2, 5, 3, 6, 4, 7, 8, 9] [0, 1, 2, 3, 5, 6, 4, 7, 8, 9] [0, 1, 2, 3, 5, 6, 4, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
