目录

🛴基本介绍

算法思想

🛹实例

思路分析

 代码实现

 🛵算法性能分析

🛴基本介绍

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为见效增量排序。

希尔排序的时间复杂度比直接插入排序的时间复杂度小，他与直接插入排序的不同在于它会优先比较距离较远的元素。

算法思想

希尔排序是按照一定的增量进行分组排序，对每组使用直接插入排序算法排序;随着分组个数的减少，每组中元素就会越来越多，当增量减少为1时，排序结束。

🛹实例

原始数组：[8,9,1,7,2,3,5,4,6,0]

分组的个数与数据个数有关。一般情况下，选择增量为gap=length/2

分组的个数一般为奇数个，因为偶数组会存在重复排序，所以分组个数为奇数组

思路分析

第一趟排序：初始增量gap=length/2=5，即将整个数组分为五组，对这五组分别进行直接插入排序

 第二趟排序：然后缩小增量，gap=5/2=2，数组被分为两组，对这两组分别进行直接插入排序

第三趟排序：

再缩小增量为gap=2/2=1，此时整个数组为1组，进行直接插入排序，结果如下：

 代码实现

public class ShellSort {    public static void main(String[] args) { int []arr={8,9,1,7,2,3,5,4,6,0}; shellSort(arr); System.out.println("排序后的数组为："+Arrays.toString(arr));    }    private   static  void  shell(int[]arr,int gap){ if (arr==null||arr.length==1){     return; } //从第二个元素开始，和前面的有序表进行比较 for (int i=1;i=0;j-=gap){  if (arr[j]>temp){      arr[j+gap]=arr[j];//后移一个位置  }  else {      break;  }     }     arr[j+gap]=temp; }    }    public  static  void  shellSort(int []arr) { int[] gaps = {5, 3, 1}; for (int i = 0; i < gaps.length; i++) {     shell(arr, gaps[i]); }    }}

运行结果:

 🛵算法性能分析

时间复杂度：O（n^1.3-1.5）

空间复杂度：O（1）

稳定性：不稳定