本文介绍了两种插入排序算法：直接插入排序和希尔排序。 其中直接插入排序是一种比较基础的排序方法，容易理解，但效率不高。 希尔排序是直接插入排序的改进版，虽然不太理解，但是实现后的效率比直接插入排序有很大的提高。
接下来详细说明这两种排序算法的思路和实现代码。 接下来介绍一下。
文章目录1 .插入的思想2 .直接插入排序3 .希尔排序(缩小增量排序) )。
1 .插入的思想
基本想法：
插入排序是一种基本的排序方法，将待排序的数据按关键码值大小逐个插入已排序的有序序列中，得到新的有序序列，直到插入所有记录。
实际上，我们在打牌的时候，使用了插入顺序的思想。
2 .直接插入排序的基本思路：
直接插入排序：插入第I(I=1)个元素时，先前的array[0]、array[1]、array[i-1]已经排序。 此时，使用Array[i]的排序代码和array[i-1]、array
虽然光靠文字可能很难理解，但接下来将通过图解来说明直接插入排序的算法的想法。
让我们先看一下插入排序：
下图是插入排序的一系列序列。
这里试着按照升序排列五个数。 仔细一看，前4个数是已经确定顺序的数组组，取出第5个数2插入到前面顺序的数组中属于它的位置即可。
的插入过程是比较2和6到前面的各数。 这里是按照升序排列的，所以如果2小于当前数，则将当前数向后移动一位，继续比较下一个数。 为了插入，这个要素需要插入到比他大的要素和比他小的要素之间，所以比他大的要素向后错开一位，留出空间。 如果2大于当前数，请在当前数之后插入2
动态演示如下。
上图是插入排序的演示，理解起来并不太难。
但是，一次插入排序的前提是插入的序列必须有序。 那么，如何对一组完全无序的序列进行插入排序呢？
主要方法是采用上述思路，多次插入该组数据进行排序即可。
如下图所示。
第一次顺序时，首先在前面的列中插入这组数的第二位。 此时，第二位数前面只有一个数，所以默认情况下可以排序。 此时，使用以上插入顺序的想法，可以将第二个个数插入到由第一个数据构成的系列中。
第一列结束后，第二列排序时，拿着第三位数往前插入，这时，第一列的插入排序中前两个个数按顺序排列，可以直接插入排序。
按顺序，在前一个序列中插入最后一个数，然后插入排序就完成了。
具体思想是这样的。 实现代码如下。
voidinsertsort(int*a，int n ) ) assert ) a； for(intI=0； i n - 1； I ) )//end1的数据存储在[0，end]的有序区间int end=i； int tmp=a[end 1]； while(end=0) if ) tmpa[end] ) {a[end 1]=a[end]； --end； }else{break； }}a[end 1]=tmp； }定义为最初插入end的数量之前的数量，定义为插入tmp的数量。
然后检查并比较end和end之前的数量和tmp。 如果当前数大于要插入的数tmp，则将当前数向后移动一位，end- -准备比较下一个数。
在当前数小于要插入的数tmp的情况下，结束循环，结束后将tmp中存储的值配置在当前数end的上位。
[0，end]始终保持秩序，将end 1插入[0，end]区间，保持秩序。
最后，在外部写出以最初插入位置前一个位置为0、最后插入位置前一个位置为n - 2的循环控制循环。
直接插入排序的特性总结：
1 .元素集合越接近有序，直接插入排序算法的时间效率越高。 2 .时间复杂度： o(n )3.空间复杂度： o )1)是一种稳定的排序算法。 4 .稳定性：稳定性3 .水蛭排序(缩小增量排序)水蛭排序又称缩小增量法。 希尔排序的基本思想是首先选择整数，将待排序文件中的所有记录分成组，将距离选定数量的所有记录分成同一个组，然后对每个组中的记录进行排序。 然后，取而代之，重复上述按组合排序的作业。 当选常数达到1时，统一排列内记录的所有数按顺序排列。
希尔排序实际上是直接插入排序的改进方法，如上所述，直接插入排序时，序列越接近有序，直接插入排序算法的时间效率越高。 因此，希尔排序首先进行多次预排序，逐渐使数组接近有序，最后直接插入数组进行排序。
首先，让我们看一下预排序的方法。 首先选择距离gap，然后将元素间距为gap的元素分成组，然后直接插入每个元素组进行排序。
例如，如果按gap为3的段对以下序列进行排序，则图中颜色相同的元素将成为一组。
然后，我们将原始序列与排序后的序列进行比较。
说得通
过对比观察可以发现，先进行一趟预排序之后的序列要越接近有序，因为较大的数被尽可能的放在了后面，较小的数被尽可能的放在了前面。同时还有一点需要注意：
gap越大，前面大的数据可以越快到后面，后面小的数可以越快到前面，但是gap越大，一趟排序后的序列越不接近有序。gap越小，一趟排序后的序列越接近有序，如果gap == 1其实就相当于直接插入排序，一趟之后直接变成有序。这里可以发现，gap的越大和越小都有各自的优缺点，那么怎样合理的设置gap的值呢？
在当年经过希尔的多次检验之后发现，gap的值依次减小为原来的1/3，直至减小到1这样算法的效率最高。
接下来我们来看一次完整希尔排序的示意图：
知道了这些之后来看代码：
一开始先定义gap的值为0，然后每进行一趟排序让gap的值缩小3倍，直至减小到1.
代码中有有几点需要注意：
第一：进行一趟值为gap的直接插入排序时，并不是单独拿出一组间距为gap的值进行排序，而是从第一个下标为0的元素开始，以0和0+gap两个元素为一组进行插入排序。第二次从下标为1的元素开始，以1和1+gap两个元素为一组进行插入排序。依次类推，直至排到第n-gap-1个元素为止(可以参考上面的动图演示)。
第二，最后一趟排序时gap的值一定要等于1，这样才能完整的对这组数据进行一次直接插入排序，从而确保排序的正确性。因此在除以3的时候记得要加上1，这是为了确保最后一次排序一定是gap为1的直接插入排序。如果不这样做，可能最后一次排序时的gap == 2，然后再除以3等于0结束循环，这样就没有最后进行直接插入排序，不能保证排序的结果为正确的。
接下来我们将每一趟希尔排序后的序列打印出来进行观察，只需在每一趟排序之后加上一个打印函数：
void PrintArray(int* a, int n){for (int i = 0; i < n; ++i){printf("%d ", a[i]);}printf("n");}void ShellSort(int* a, int n){// 1.gap>1相当于预排序，让数组接近有序// 2.gap==1就相当于直接插入排序，保证有序int gap = n;while (gap > 1){gap = gap / 3 + 1; // +1保证了最后一次gap一定是1// gap == 1最后一次就相当于直接插入排序for (int i = 0; i < n - gap; ++i){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}PrintArray(a, n);}}void TestShellSort(){int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };PrintArray(a, sizeof(a) / sizeof(int));ShellSort(a, sizeof(a) / sizeof(int));}int main(){TestShellSort();return 0;}运行结果：
可以看到每一趟排序之后都越来越接近有序，从而大大提高了直接插入排序的效率。
希尔排序的特性总结：
1.希尔排序是对直接插入排序的优化。2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试对比。3.希尔排序的时间复杂度不好计算，需要进行推导，推导出来的时间复杂度为：O（N^1.3 - N²）。本篇文章到这里就结束了，希望能对大家有所帮助。如果觉得哥们写的还行的话，就帮忙点个赞吧，谢谢。