前言

1.插入排序，一般也被称为直接插入排序。对于少量元素的排序是一个好的排序方法。插入排序是一种最简单的排序方法。

2.它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

一、概述

插入排序：每次将一个待排序的记录，按其关键字的大小插入到前面已排序好的记录序列中的适当位置，直到全部记录插入完成为止。

确定插入位置的查找方法不同导致不同的算法描述：

直接插入排序：基于顺序查找
希尔排序：基于逐趟缩小增量

二、希尔排序

1、希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

2、希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

1）概述

希尔排序：Shell Sort
希尔排序，又称为缩小增量排序。
基本思路：

1.先选取一个小于n的整数di（称为增量），并将记录序列分成若干子表

2.从下标为0的记录开始，间隔为di的记录组成一个子表，在各个子表内进行直接插入排序。

3.一趟完成后，逐步减小增量di，并重复上面的步骤，直到di=1，使得间隔为1的记录有序，也就是整个序列都达到有序。

2）示意图

3）例题分析

序列：52、39、67、95、70、8、25、52、56、5

序列：99、5、69、33、56、13、22、55、77、48、12、88、2、69、99

4）算法实现

代码

//【算法3】希尔排序算法
public void shellSort(int[] d) { //d[]为增量数组
    RecordNode temp;
    int i, j;
    System.out.println("希尔排序");
    //控制增量，增量减半，若干趟扫描
    for (int k = 0; k < d.length; k++) {
        //一趟中若干子表，每个记录在自己所属子表内进行直接插入排序
        int dk = d[k];
        for (i = dk; i < this.curlen; i++) {
            temp = r[i];
            for (j = i - dk; j >= 0 && temp.key.compareTo(r[j].key) < 0; j -= dk) {
                r[j + dk] = r[j];
            }
            r[j + dk] = temp;
        }
        System.out.print("增量dk=" + dk + "  ");
        display();
    }
}

测试

public class TestSeqList3_shell {
    public static void main(String[] args) throws Exception {
        int[] arr = {52,39,67,95,70,8,25,52,56,5};
        int[] d = {5,3,1};
        SeqList seqList = new SeqList(arr.length);
        for (int i = 0; i < arr.length; i++) {
            seqList.insert(i, new RecordNode(arr[i]));
        }
        // 希尔排序算法
        seqList.shellSort(d);
    }
}
//希尔排序
//增量dk=5    8 25 52 56  5 52 39 67 95 70
//增量dk=3    8  5 52 39 25 52 56 67 95 70
//增量dk=1    5  8 25 39 52 52 56 67 70 95

5）性能分析

希尔排序的时间复杂度：不确定，但在插入排序中，希尔排序的效能最高，最好情况可达O(nlog2n)

只需要一个记录的辅助空间，O(1)

是==不稳定==的排序方式，也就是说 52和 52 顺序不确定。

写到最后

四季轮换，已经数不清凋零了多少，愿我们往后能向心而行，一路招摇胜！

🐋 你的支持认可是我创作的动力

💟 创作不易，不妨点赞💚评论❤️收藏💙一下

😘 感谢大佬们的支持，欢迎各位前来不吝赐教

【数据结构】插入排序 — 希尔排序

前言

一、概述

二、希尔排序