Java八大排序之希尔（Shell）排序

电玩女神 2023-08-17 16:31 134阅读 0赞

**希尔排序**(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

Shell插入排序的具体做法是：对有n个记录进行排序，首先取1个整数d<n，将这n个记录分成d组，所有位置相差为d的倍数的记录分在同一组，在每组中使用直接插入排序进行组内排序，然后缩小d的值，重复进行分组和组内排序，一直到d=1结束。

**执行过程图：**

![1703996-20190817131253395-494250232.jpg][]

**代码：**

1 public class TestShell {
     2     //插入排序
     3     public static void shellSort(int[] arrays){
     4         int d,j,temp;
     5         d = arrays.length/2;
     6         //增量大于等于1
     7         while(d>=1){
     8             //从第d个元素开始，将所有元素有序插入相应分组中
     9             for (int i = d; i < arrays.length; i++){
    10                 temp = arrays[i];   //保存第i个元素
    11                 j = i - d;      //向前找插入位置
    12                 while(j>=0 && temp < arrays[j]){    //排序码比较找插入位置并后移
    13                     arrays[j+d] = arrays[j];    //记录后移
    14                     j = j - d;      //继续向前查找
    15                 }
    16                 arrays[j+d] = temp;     //插入第i个元素的副本
    17             }
    18             d = d/2;
    19             System.out.println(Arrays.toString(arrays));
    20         }
    21         System.out.println("最后排序："+Arrays.toString(arrays));
    22     }
    23     public static void main(String[] args) {
    24         int[] arrays={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
    25         shellSort(arrays);
    26     }
    27 }

**测试结果：**

[1, 38, 34, 12, 164, 11, 18, 49, 78, 65, 97, 176, 213, 227, 49]
    [1, 38, 11, 12, 49, 34, 18, 97, 49, 65, 164, 78, 213, 227, 176]
    [1, 11, 12, 18, 34, 38, 49, 49, 65, 78, 97, 164, 176, 213, 227]
    最后排序：[1, 11, 12, 18, 34, 38, 49, 49, 65, 78, 97, 164, 176, 213, 227]

**时间复杂度：** Shell排序一般而言要比直接插入排序快，但要给出时间复杂度的分析相当难。至今为止也没有找到最好的缩小增量序列的选取方法。

借用别人一句话：

最坏情况下，每两个数都要比较并交换一次，则最坏情况下的时间复杂度为O（n2）, 最好情况下，数组是有序的，不需要交换，只需要比较，则最好情况下的时间复杂度为O（n）。

经大量人研究，希尔排序的平均时间复杂度为O（n1.3）（这个我也不知道咋来的，书上和博客上都这样说，也没找到个具体的依据，，，）。

**结语：**优缺点去百度百科就可以知道了，我就不复制粘贴了[https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin\#5\_1][https_baike.baidu.com_item_E5_B8_8C_E5_B0_94_E6_8E_92_E5_BA_8F_3229428_fr_aladdin_5_1]

转载于:https://www.cnblogs.com/mtgh/p/11368465.html

[1703996-20190817131253395-494250232.jpg]: /images/20230810/6ae32a02398a4079878742fdd693f3c4.png
[https_baike.baidu.com_item_E5_B8_8C_E5_B0_94_E6_8E_92_E5_BA_8F_3229428_fr_aladdin_5_1]: https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin#5_1