目录

希尔排序

lienhui68 收录于技术

2020-06-12 约 1033 字预计阅读 3 分钟次阅读

目录

基本介绍

插入排序适合小规模数据或者基本有序的情况，希尔排序是插入排序的改进版，实现简单，对于中等规模数据的性能表现还不错。希尔排序也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

算法流程

首先它把较大的数据集合分割成若干个小组（逻辑上分组）10/2=5组，然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高。每个分组进行插入排序后，各个分组就变成了有序的了，此时整个数组变的部分有序。注意: 对每个小组分别进行插入排序并不是先对一个组进行排序完再对另一个组进行排序，而是轮流对每个组进行插入排序。插入顺序表现为1-1,2-1,3-1,1-2,2-2,3-2,1-3,2-3,3-3，其中a-b表示a组第b个元素。
然后缩小增量为上个增量的一半 5/2 = 2:继续划分分组，此时，每个分组元素个数多了，但是，数组变的部分有序了。
最后设置增量为1，则整个数组被分为一组，此时，整个数组已经接近有序了，插入排序效率高，对这仅有的一组数据进行排序，排序完成。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


 /**
     * 希尔排序
     *
     * @param arr
     */
    public static void hillSort(int[] arr) {
        // 分组，先分成gap=n/2，再分成n/2/2 直到只剩下一组,逻辑分组内的元素是i，i+gap,... gap即是分组数量也是步长(同组内两个元素的间距)
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 进行插值排序，注意这里排序不是一组排序完再排序下一组而是轮流排序，插入顺序表现为：1-1,2-1,3-1,1-2,2-2,3-2,1-3,2-3,3-3
            // 下面这个和插入排序几乎一样，当gap=1表示最后一组时，也就是简单插入排序
            for (int i = gap; i < arr.length; i++) {
                int insertVal = arr[i];
                int j = i - gap;
                for (; j >= 0 && insertVal < arr[j]; j -= gap) {
                    // 有序列表中的元素后移
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = insertVal;
            }
        }
    }

时间复杂度

希尔排序的时间复杂度极其复杂，有的增量序列的复杂度至今还没有人能证明出来。希尔排序的复杂度和增量序列是相关的{1,2,4,8,…}这种序列并不是很好的增量序列，使用这个增量序列的时间复杂度（最坏情形）是O(n^2)。 Hibbard提出了另一个增量序列{1,3,7，…,2^k-1}，这种序列的时间复杂度(最坏情形)为O(n^1.5) Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是{1,5,19,41,109,…}

参考

希尔排序–简单易懂图解 https://blog.csdn.net/qq_39207948/article/details/80006224