排序算法-希尔排序(Shell Sort)

灰太狼 2023-07-02 04:25 14阅读 0赞

### 文章目录 ###

*   *   *  希尔排序法介绍
         *  希尔排序法算法
         *  时间复杂度
         *  稳定性
         *  其他排序法的比较

### 希尔排序法介绍 ###

希尔排序法(Shell Sort)是**D.L.Shell**于1959年提出的一种排序算法，是[直接插入排序法][Link 1]的更高效的改进版。在这之前的排序算法如[冒泡排序][Link 2]、[简单选择排序][Link 3]、[直接插入排序][Link 1]等算法的的时间复杂度都为 O ( n 2 ) O(n^\{2\}) O(n2)，而希尔排序突破了这一时间复杂度。  
【原理】  
直接插入排序算法比冒泡排序和简单选择排序性能都要高，尤其在序列基本有序并且记录数相对较少的情况，只需要简单的几个插入动作就能完成排序。

希尔排序的思路就是在插入排序算法的基础上，创造插入排序算法的有利条件，将序列按照某个增量分成多个子序列进行插入排序，使整个序列变为基本有序，并且由于按照增量分了子序列，所以每个子序列的记录数变少了，增量和子序列长度成反比，增量从小于n的某个值每次递减，子序列随增量变小而变长。直到增量变为1，使其所有记录为一个整体序列然后进行一次插入排序为止。

什么才叫基本有序呢？比如\{2,1,4,3,5,6,8,7,9\}可以说是基本有序，小的数字基本在序列的前部，不大不小的在中部，大的数字在后部。 \{8,7,6,3,9,2,4,5,1\}这样的序列就不是基本有序，因为1在序列的最后，9在中间，8在第一位，所以谈不上是基本有序的。

【例子】  
下面看个对关键字序列\{8,7,1,9,3,6,4,5,2\}进行希尔排序的步骤。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70]

### 希尔排序法算法 ###

public static void shellSort(Integer[] arr) { 
        int increment = arr.length;
        do { 
            increment = increment / 3 + 1;
            for (int i = increment; i < arr.length; i++) { 
                if (arr[i-increment] > arr[i]){ 
                    int minIdx = i;
                    int compIdx = minIdx-increment; //需往右边移动的关键字下标
                    int minValue = arr[minIdx];
                    while (compIdx >= 0 && arr[compIdx] > minValue) {  //比较大小
                        arr[minIdx] = arr[compIdx]; //关键字右移
                        minIdx = compIdx;
                        compIdx = compIdx - increment;
                    }
                    arr[minIdx] = minValue; //插入关键字
                }
            }
        } while (increment > 1);
    }

### 时间复杂度 ###

希尔排序的时间复杂度依赖增量序列，增量的取值至今还是个难题，大量研究表明，当增量序列为delta\[k\]= 2 t − k + 1 2^\{t-k+1\} 2t−k\+1\-1(0 ⩽ \\leqslant ⩽k ⩽ \\leqslant ⩽t ⩽ ⌊ l o g 2 ( n + 1 ) ⌋ \\leqslant \\left \\lfloor log2(n+1) \\right \\rfloor ⩽⌊log2(n\+1)⌋) 时，可以获得不错的效率，其时间复杂度为 O ( n 3 / 2 ) O(n^\{3/2\}) O(n3/2)，要好于直接插入排序的 O ( n 2 ) O(n^\{2\}) O(n2)。

### 稳定性 ###

由于按照增量跳跃式分成了子序列插入排序，所以相同值位置可能会被替换，所以希尔排序是不稳定的。

### 其他排序法的比较 ###

以下分别使用[简单选择排序法][Link 3]、[直接插入排序法][Link 1]和希尔排序法对10万随机关键字的排序耗时，从结果可以看出直接插入排序的执行时间比简单选择排序法快，而希尔排序法比直接插入排序法快了非常多只用了38ms。

简单选择排序执行时间:8077ms
    直接插入排序执行时间:4408ms
    希尔排序执行时间:38ms

[Link 1]: https://blog.csdn.net/u013632755/article/details/103943811
[Link 2]: https://blog.csdn.net/u013632755/article/details/103899982
[Link 3]: https://blog.csdn.net/u013632755/article/details/103916149
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200128212923660.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM2MzI3NTU=,size_16,color_FFFFFF,t_70