诞生的背景

什么背景下诞生了该技术？

希尔排序（Shell Sort）是一种插入排序的改进算法，它通过将数据分成多个小组来排序，然后逐渐减小这些小组的间隔，直到最后一次使用标准的插入排序算法。希尔排序的时间复杂度取决于使用的间隔序列，通常为 O(n^1.5) 到 O(n^2)。以下是希尔排序的代码示例和时间空间复杂度分析，希望对大家有所帮助。北京木奇移动技术有限公司，专业的软件外包开发公司，欢迎交流合作。

希尔排序是基于插入排序的。

插入排序缺点：当一个较小的数，在数组的右侧，则需要将所有的中间数据都向右移动。

为了解决这个问题，希尔排序则是通过加大插入排序的间隔，将间隔的元素进行插入排序。为了便于理解，如下图所示有7个元素。首先计算间隔h=3*h+1，可以算出h为2，那么从第一个元素依次间隔2个元素进行插入排序，得到第二行的数组。

希尔排序

一、插入排序

思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。

关键问题：在前面已经排好序的序列中找到合适的插入位置。

前言

在数据结构和算法中，排序是非常重要的一环，并且排序也是渗透编程的方方面面。

在这里插入图片描述

你或许在写一个sql的order by按照某组进行排序，又或者你在刷一道题时候、常常遇到贪心+自定义排序求解的思路题，或者变态的面试官让你手写快排，又或者是app的姓氏升降序列 - - -

如果需要查看排版好看的请搜索微信公众号放开我我还能学

前言

之前我们曾经介绍了选择类排序中的简单选择排序，它的时间复杂度是O(n^2)。这次我们介绍插入类排序中的

接下来我们来看一下希尔排序。关于希尔排序，首先希尔排序是插入排序的一种改进，所以如果你们还不太清楚插入排序，请看我上一个视频插入排序。在理解了插入排序之后，再来理解希尔排序就非常简单了，我们来看一下它的思路。

·首先这是一个无序数组，我们首先把这个长度为8的数组拆分成4组，它直接长度除以2，得到了一个一组增量4。其实就是分成四组，比如说5和3一个组，1和6一个组，9和4一个组，8和7一个组，分成四组。

抛砖引玉

十大经典排序算法江山图

排序算法的衡量指标我这里不再重复，上一篇我已经列举分析的很清楚了，但是非常重要，没看到我上一篇的小伙伴墙裂推荐，这里给一个直通车票 极客算法训练笔记(五)，十大经典排序之冒泡，选择，插入排序 。