1、希尔排序简介

希尔排序，是插入排序的一种进阶排序算法，通过一个不断缩小的增量序列，对无序序列反复的进行拆分并且对拆分后的序列使用插入排序的一种算法，所以也叫作“缩小增量排序”或者“递减增量排序”。既然希尔排序也是使用插入排序进行序列排序操作的，为什么会有希尔排序呢？

这是基于插入排序的两点性质而来：
对一个“几乎”已经排好序的无序序列，插入排序的效率是很高的，可以达到线性排序的效率。比如，当序列中只有一位元素没有在适当的位置，那么整个序列只需要移动该序列的位置即可达到完成排序的任务。
但是一般的无序序列不是一个“几乎”已经排好序的序列，所以插入排序是低效的。因为它每次只能移动一位元素。

基于以上两点出现了希尔排序，那么希尔排序到底如何利用了这两个性质呢？

概述
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。


插入排序
思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置，直到全部插入排序完为止。
关键问题：在前面已经排好序的序列中找到合适的插入位置。
方法：

直接插入排序
二分插入排序
希尔排序
直接插入排序
① 基本思想

每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。



② 算法实现

首先需要定义一个待排序的数组：

int a[] = {3,1,5,7,2,4,9,6,10,8};
1
    /**
     * 直接插入排序
     * @param v
     */
    public void insertSort(View v) {
        for (int i = 1; i < a.length; i++) {
            // 待插入元素
            int temp = a[i];
            int j;
            for (j = i - 1; j >= 0 && a[j] > temp; j--) {
                // 将大于temp的往后移动一位
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
    }

③ 复杂度

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

时间复杂度：O（n^2）
空间复杂度：O（1）
2、希尔排序的步骤

首先根据初始序列的长度，选定一个递减增量序列t1，t2，t3......tk，其中ti>tj，tk = 1。
根据选定的增量序列元素个数k，对初始序列进行k趟排序。
根据增量序列的值ti，每趟排序会把初始序列划分成若干个元素的子序列，然后对这些子序列使用插入排序，因为这是递减增量序列，所以第一趟的排序，增量值最大，那么划分的子序列数量也就最多，每个子序列的元素也就越少，可以看做是一个“几乎”已经排好序的序列，当增量值越来越小的时候，子序列数量也就越少，每个子序列的元素也就越多，但是，基于前几次的排序，这些子序列虽然元素多，但是已经是一个“几乎”排好序的序列了，当最后一次排序的时候，即增量序列的值为1时，就是对整个无序序列进行排序，这时整个序列已经是一个“几乎”排好序的序列了。

以图为例进行说明，假设给定的初始无序序列如下：
4     5     8     2     3     9     7     1

首先，我们选择一个增量序列，这个增量序列如何选择呢？首先我们得保证第一次的所有子序列元素数量应该至少保证为2个或以上，这样是用插入排序才有意义，如果元素数量为1，也就是增量序列的第一个值为初始序列的长度或者更大，那么这次遍历将“无功而返”，所以至少应该保证子序列元素数量为2或以上，当子序列数量退化到初始序列长度时，希尔排序也退化成了插入排序。事实上，希尔排序的效率依赖于增量序列的选择，好的增量序列可以大大的提高希尔排序的效率，但是增量序列的选择是和初始序列有关系的。


一个好的递减增量序列选取的标准是：第一、递减增量序列最后一个值应该为1；第二、递减增量序列中的值，尤其是相邻的值最好不要互为倍数的关系，如果是互为倍数的关系，那么根据这两个序列值的分组将会有重复的情况，可能会做“无用功”。


该示例中，我们选取的递减增量序列位[3,2,1]。
递减增量序列已经有了，下面开始进行3趟（增量序列长度为3）排序，先取增量序列第一个值3，然后将初始序列分组，如下：

对三组子序列[4,2,,7]，[5,3,1]，[8,9]分别使用插入排序，结果如下：



然后，对该序列再次进行增量序列的分组，这次增量序列的值为2，分组情况如下：

对两组子序列分别使用插入排序，结果如下：

最后，对整个序列做插入排序（增量序列值为1）即可。

从整个过程可以看出，每次的排序，都会将较小的值转移到序列的前边，整个序列的有序性不断的变强，可以使插入排序达到更高的效率。
二分插入排序
① 基本思想

二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。



② 算法实现

    /**
     * 二分插入排序
     * @param v
     */
    public void twoInsertSort(View v) {
        for (int i = 0; i < a.length; i++) {
            int temp = a[i];
            int left = 0;
            int right = i - 1;
            int mid;
            while (left <= right) {
                mid = (left + right) / 2;
                if (temp < a[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                a[j + 1] = a[j];
            }
            if (left != i) {
                a[left] = temp;
            }
        }
    }

希尔排序
① 基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-1《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。



② 算法实现

    /**
     * 希尔排序
     * @param v
     */
    public void shellSort(View v) {
        int dk = a.length/2;
        while(dk >= 1){
            ShellInsertSort(a, dk);
            dk = dk/2;
        }
        after.setText(getText(a));
    }
    private void ShellInsertSort(int[] a, int dk) {//类似插入排序，只是插入排序增量是1，这里增量是dk,把1换成dk就可以了
        for (int i = dk; i < a.length; i++) {
            // 待插入元素
            int temp = a[i];
            int j;
            for (j = i - dk; j >= 0 && a[j] > temp; j = j-dk) {
                // 将大于temp的往后移动dk位
                a[j + dk] = a[j];
            }
            a[j + dk] = temp;
        }
    }

③ 复杂度

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

时间复杂度：O（nlog2n）
空间复杂度：O（1）

1、希尔排序简介

希尔排序，是插入排序的一种进阶排序算法，通过一个不断缩小的增量序列，对无序序列反复的进行拆分并且对拆分后的序列使用插入排序的一种算法，所以也叫作“缩小增量排序”或者“递减增量排序”。既然希尔排序也是使用插入排序进行序列排序操作的，为什么会有希尔排序呢？

这是基于插入排序的两点性质而来：
对一个“几乎”已经排好序的无序序列，插入排序的效率是很高的，可以达到线性排序的效率。比如，当序列中只有一位元素没有在适当的位置，那么整个序列只需要移动该序列的位置即可达到完成排序的任务。
但是一般的无序序列不是一个“几乎”已经排好序的序列，所以插入排序是低效的。因为它每次只能移动一位元素。

基于以上两点出现了希尔排序，那么希尔排序到底如何利用了这两个性质呢？

概述
排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。


插入排序
思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置，直到全部插入排序完为止。
关键问题：在前面已经排好序的序列中找到合适的插入位置。
方法：

直接插入排序
二分插入排序
希尔排序
直接插入排序
① 基本思想

每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。



② 算法实现

首先需要定义一个待排序的数组：

int a[] = {3,1,5,7,2,4,9,6,10,8};
1
    /**
     * 直接插入排序
     * @param v
     */
    public void insertSort(View v) {
        for (int i = 1; i < a.length; i++) {
            // 待插入元素
            int temp = a[i];
            int j;
            for (j = i - 1; j >= 0 && a[j] > temp; j--) {
                // 将大于temp的往后移动一位
                a[j + 1] = a[j];
            }
            a[j + 1] = temp;
        }
    }

③ 复杂度

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

时间复杂度：O（n^2）
空间复杂度：O（1）
2、希尔排序的步骤

首先根据初始序列的长度，选定一个递减增量序列t1，t2，t3......tk，其中ti>tj，tk = 1。
根据选定的增量序列元素个数k，对初始序列进行k趟排序。
根据增量序列的值ti，每趟排序会把初始序列划分成若干个元素的子序列，然后对这些子序列使用插入排序，因为这是递减增量序列，所以第一趟的排序，增量值最大，那么划分的子序列数量也就最多，每个子序列的元素也就越少，可以看做是一个“几乎”已经排好序的序列，当增量值越来越小的时候，子序列数量也就越少，每个子序列的元素也就越多，但是，基于前几次的排序，这些子序列虽然元素多，但是已经是一个“几乎”排好序的序列了，当最后一次排序的时候，即增量序列的值为1时，就是对整个无序序列进行排序，这时整个序列已经是一个“几乎”排好序的序列了。

以图为例进行说明，假设给定的初始无序序列如下：
4     5     8     2     3     9     7     1

首先，我们选择一个增量序列，这个增量序列如何选择呢？首先我们得保证第一次的所有子序列元素数量应该至少保证为2个或以上，这样是用插入排序才有意义，如果元素数量为1，也就是增量序列的第一个值为初始序列的长度或者更大，那么这次遍历将“无功而返”，所以至少应该保证子序列元素数量为2或以上，当子序列数量退化到初始序列长度时，希尔排序也退化成了插入排序。事实上，希尔排序的效率依赖于增量序列的选择，好的增量序列可以大大的提高希尔排序的效率，但是增量序列的选择是和初始序列有关系的。


一个好的递减增量序列选取的标准是：第一、递减增量序列最后一个值应该为1；第二、递减增量序列中的值，尤其是相邻的值最好不要互为倍数的关系，如果是互为倍数的关系，那么根据这两个序列值的分组将会有重复的情况，可能会做“无用功”。


该示例中，我们选取的递减增量序列位[3,2,1]。
递减增量序列已经有了，下面开始进行3趟（增量序列长度为3）排序，先取增量序列第一个值3，然后将初始序列分组，如下：

对三组子序列[4,2,,7]，[5,3,1]，[8,9]分别使用插入排序，结果如下：



然后，对该序列再次进行增量序列的分组，这次增量序列的值为2，分组情况如下：

对两组子序列分别使用插入排序，结果如下：

最后，对整个序列做插入排序（增量序列值为1）即可。

从整个过程可以看出，每次的排序，都会将较小的值转移到序列的前边，整个序列的有序性不断的变强，可以使插入排序达到更高的效率。
二分插入排序
① 基本思想

二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。



② 算法实现

    /**
     * 二分插入排序
     * @param v
     */
    public void twoInsertSort(View v) {
        for (int i = 0; i < a.length; i++) {
            int temp = a[i];
            int left = 0;
            int right = i - 1;
            int mid;
            while (left <= right) {
                mid = (left + right) / 2;
                if (temp < a[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            for (int j = i - 1; j >= left; j--) {
                a[j + 1] = a[j];
            }
            if (left != i) {
                a[left] = temp;
            }
        }
    }

希尔排序
① 基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2《d1重复上述的分组和排序，直至所取的增量dt=1(dt《dt-1《…《d2《d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。



② 算法实现

    /**
     * 希尔排序
     * @param v
     */
    public void shellSort(View v) {
        int dk = a.length/2;
        while(dk >= 1){
            ShellInsertSort(a, dk);
            dk = dk/2;
        }
        after.setText(getText(a));
    }
    private void ShellInsertSort(int[] a, int dk) {//类似插入排序，只是插入排序增量是1，这里增量是dk,把1换成dk就可以了
        for (int i = dk; i < a.length; i++) {
            // 待插入元素
            int temp = a[i];
            int j;
            for (j = i - dk; j >= 0 && a[j] > temp; j = j-dk) {
                // 将大于temp的往后移动dk位
                a[j + dk] = a[j];
            }
            a[j + dk] = temp;
        }
    }

③ 复杂度

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

时间复杂度：O（nlog2n）
空间复杂度：O（1）