Java：希尔排序

1.步骤

将一组数组以 gap 为单位，将数组分为 n / gap 组。如图。

将每一组的数据按照对应的大小进行排序。再将 gap 的值逐渐小。gap 的每一次减小都对数组进行一次排序直至 gap == 1。gap 的初始值没有定论，可以取 gap = n / 2 ，也可以取 gap = n / 3 等等。

2.代码

public static void ShellSort(int[] arr) {int gap = arr.length;while(gap > 1) {gap /= 2;shell(arr,gap);}
}
public static void shell(int[] arr,int gap) {for(int i = gap; i < arr.length; i++) {int j = i - gap;int temp = arr[i];for(; j >= 0; j-= gap) {if(temp < arr[j]) {arr[j + gap] = arr[j];}else {break;}}arr[j + gap] = temp; }
}