先说思路
先把数组分成一个个的小的数组,在数组内排序后,在划分较大一点的数组,在数组内再排序,最后成为一个数组
希尔的目的是防止插入排序的最后是最小的数,要移动全部的数组导致的浪费,所以尽可能的让每个小组的小数在前面,这样移动的时候不至于移动太多次
希尔有两种实现方式
1.交换法 不推荐
时间消耗极高
//交换式
public static void shell1(int[] arr){
int temp = 0;
for (int gap = arr.length / 2; gap > 0 ; gap /= 2){
for (int i = gap ; i < arr.length ; i ++){
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));
}
}
问题在于每次比较只要满足条件都会交换,浪费时间
2。移位法 推荐
实质是先分组再插入,记录这个数字,然后进行比较,如果不满足就依次覆盖,最后满足或者跳出循环后再把记录的数字赋值
//移位法
public static void shell2(int[] arr){
for (int gap = arr.length/2;gap > 0 ; gap /= 2){
//插入排序
for (int i = gap ; i < arr.length;i++){
int j = i;
int temp = arr[j];
if (arr[j] < arr[j - gap]){
while (j - gap >= 0 && temp < arr[j - gap]){
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
System.out.println("==============");
System.out.println(Arrays.toString(arr));
}
}
时间消耗大大降低



