什么是希尔排序(Shell's Sort)
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
图解希尔排序
希尔排序目的为了加快速度改进了插入排序，交换不相邻的元素对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
在此我们选择增量 gap=length/2，缩小增量以 gap = gap/2 的方式，用序列 {n/2,(n/2)/2...1} 来表示。
- 初始增量第一趟 gap = length/2 = 4。
image.png
- 增量缩小为2。
image.png
- 增量缩小为1,得到最终排序结果。
image.png
代码实现
官方代码
package demo.sort;
import java.util.Arrays;
public class ShellSort {
//降序排列
public static void main(String[] args) {
int[] arr ={7,6,9,3,1,5,2,4};
sort1(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort2(int[] arr){
//初始步长是为数组的一半.直到步长为1
for(int gap = arr.length/2;gap > 0;gap = gap/2){
//从第二个步长的数据,开始向后遍历,向前做插入排序,因为第一个步长内的数据,不需要进行插入排序,都是默认第一个.
for(int i = gap;i<arr.length;i++){
//对当前数据,向前遍历步长,进行插入排序
int temp = arr[i];
//子循环从j开始
int j = i;
//j大于等于步长,和j-gap相比
//当前元素比前边元素大,则交换
for(;j >= gap && temp > arr[j-gap];j=j-gap){
arr[j] = arr[j-gap];
}
//最后把当前元素放入到比自己大的元素后面,比自己小的元素前面
arr[j] = temp;
}
}
}
}
输出结果
[1, 2, 3, 4, 5, 6, 7, 9]
自己根据理解写的
这种效率会低一些，多一些无用的循环。
package demo.sort;
import java.util.Arrays;
public class ShellSort {
//降序排列
public static void main(String[] args) {
int[] arr ={7,6,9,3,1,5,2,4};
sort1(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort2(int[] arr){
//对数组进行分组
//循环步长
for(int gap = arr.length/2;gap > 0;gap = gap/2){
//循环每一个分组
for(int i = gap;i < arr.length;i++){
//跟前面相同步长的比较，每一个位置，和所有之前的步长比较
for (int k = i; k >= gap; k = k - gap) {
if(arr[k] < arr[k-gap]){
swap(arr,k,k-gap);
}else{
break;
}
}
}
}
}
//交换位置
public static void swap(int[] arr,int j,int i ){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
参考教程：菜鸟教程--希尔排序
