白话算法之希尔排序

刺骨的言语ヽ痛彻心扉 2022-05-28 07:07 198阅读 0赞

> 算法第四版读书笔记  
>   
> 页码：P162（想看原书是怎么讲的，可自行去翻看）  
>   
> 作者：淮左白衣 （还是一个少年呵，可惜终将步入油腻的中年啊）  
>   
> – 2018年3月31日18:40:29

# 目录 #

*  目录
 *  如何理解希尔排序
 *  java代码实现
 *  关于上述代码第一层for循环的问题
 *  复杂度

--------------------

# 如何理解希尔排序 #

> 希尔排序是插入排序的一种变种 ； **理解了插入排序，将很好理解**

**核心思想**：使数组中，**任意**相距间隔 **h** 的元素都是**有序的**！这句话，笔者认为是理解希尔排序的核心语句了！

将原数组，**每一个间隔为 h 的元素**，划分为一组，看清楚了，不是将数组按照间隔h进行分组，而是对元素划分，在这些独立数组中使用插入排序，来完成**核心思想**，即任意相隔 h 的元素，都是有序的；

划分原数组的动作是一直进行的，直到间隔 h 为 1 了；当h=1的时候，使用插入排序，是必然可以完成整个数组的排序的 ；

**你可能会问：**既然最后h=1了，并且每次都是进行插入排序；那么跟我们之前直接使用插入排序有什么不同吗？或者我们为什么还要进行之前的分割数组呢？

我们都知道插入排序，在数组中倒置的序列很少的场景中，是占有很大优势的，甚至可以说是最快的排序算法；

我们正是利用这种倒置序列很少的优势，对一个大数组进行插入排序，很可能其中的倒置序列很多；但是对一个小的数组呢，因为输入规模小，倒置序列必然也少，这样插入排序就会很快；**这就是为什么要对原数组进行间隔为h的步长划分 ；我们要在小数组中使用插入排序 ；**

**为什么要一直划分，直到h=1呢？**  
因为每一次h，划分数组，并不是原数组的每一个元素，都会被排到；因此，需要多次划分，尽量做到尽可能多的元素，被排序过；怎么确定尽可能多的元素被排序过呢？可能聪明的你，看到这，已经发现了只要在h=1之前，原数组中有尽可能多的数组被排序过，那么最后一次扫尾h=1，就会被排的很快！因此，h的选择，可能决定着我们希尔排序算法的效率！

事实跟你想的一样，h的选择决定了希尔排序的效率！**目前希尔排序最坏的效率是 N^(3/2),是小于*N*2  N 2  的 ；**

我们把h的值，叫做 **递增序列** ； 其中书本上递增序列的选择是 h =h\*3+1 ;

--------------------

# java代码实现 #

Integer[] a = {
       12, 2, 5, 6, 77, 6, 7, 4, 87, 23};
            int N = a.length;
            int h = 1;
    // 根据当前的序列，计算出最大步长
    // 递增序列选的不同，影响希尔排序的效率
            while (h < N / 3) {
                h = h * 3 + 1;
            }
    
            //希尔排序的核心思想：将原来的数组，每一个相距h（步长）的元素，隶属于一个数组，
            // 这样原数组，就变为多个独立的数组，每次都将划分出来的数组，进行插入排序；
    // 每进行完一轮，就改变步长h，循环往复，直到步长为1，
    
    // 只要步长大于1，就继续希尔排序
            while (h >= 1) {
    // 将原数组，相隔h的元素，划分为一个数组,则原数组被划分许多数组
    // 对每一个独立的数组都进行插入排序
    // 既然在每个独立数组中进行插入排序，那么为什么步长不是h ，而是1 呢？下面会讲
                for (int i = h; i < N; i++) {
    // 对每一个独立的数组，进行插入排序
    // 插入排序的索引，从数组的第二个元素开始，这里数组的元素，是相距h的，
    // 第一个元素是0，则第二个元素是0+h ; 因此索引从h开始
    
    // 就是插入排序，只不过之前的插入排序，步长都是1，现在变为h ;
                    for (int j = i; j >= h && Example.less(a[j], a[j - h]); j -= h) {
                        Example.exch(a, j, j - h);
                    }
    
                }
    // 减少步长
                h /= 3 ;
            }
    
            Example.show(a);

--------------------

# 关于上述代码第一层for循环的问题 #

为什么步长没有像我们理解的那样，步长是h，其实上述的代码是精简版，你要是写成步长是h也行的，但是外面就需要再套一层循环了 ；

--------------------

# 复杂度 #

希尔排序，复杂度是说不清的，主要取决于递增序列的选择；但是无论选择什么，复杂度都是小于 *N*2  N 2  的 ；

--------------------