哈喽大家好，我是保护小周ღ，本期为大家带来的是常见排序算法中的插入排序，主要有直接插入排序以及它的升级版——希尔排序，包您一看就会，快来试试吧~
目录
一、直接插入排序
1.1 基本思想
在生活当中，这种排序方式处处可见。
在玩扑克牌的时候我们就会采用插入排序的思想，当我们拿起第二张牌时，就会下意识的与第一张牌进行比较，如果比第一张牌小，我们则将牌插入至第一张牌的左边，反之就插入至右边（升序）。以图为例：我们拿起一张7，发现比最后一张牌10小，自然7与10就要交换位置，交换完成后，发现7前面的数字比自己小，就不用交换了，所以就找到7的位置了。
我们会发现，在拿起一张牌准备插入时，待插入的区间已经是有序的，我们要做的是，插入后使区间依旧有序。
1.2 算法思想：
当插入第 i (i>=1)个元素时，前面的array[0],a[1]……a[i-1] 已经排序好，此时用a[i]的排序码与 a[i-1],a[i-2]……进行比较，找到插入位置，原来位置上的数据元素顺序往后移。
用一组实例来观察一下是算法是怎么实现的的：
1.3 程序实现：
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> //打印数据 void Print(int* a,int n) { for (int i=0;i<n;++i) { printf("%d ",a[i]); } printf("\n"); } //直接插入排序 void InsertSort(int *a, int n)//升序 { for (int i=0;i<n-1;++i) { int end = i; int tmp = a[end + 1];; while (end>=0) { if (a[end] > tmp)//修改此处符号即可升序降序切换 { a[end+1] = a[end]; --end; } else { break; } a[end + 1] =tmp; } } //打印数据 Print(a,n); } int main() { int a[6] = { 5,2,4,6,1,3 }; //直接插入排序 InsertSort(a,sizeof(a)/sizeof(a[0])); return 0; }
1.4 直接插入排序的总结：
1.元素集合越接近有序，直接插入排序算法时间效率越高
2.时间复杂度：O(N^2)(最坏情况) ，最好情况时间复杂度是O(N);
3.空间复杂度：O(1),是一种稳定的排序算法
4.稳定性：稳定
二、希尔排序
希尔排序是一种特殊的插入排序，是直接插入排序基础上的优化。
2.1 算法思想：
希尔排序又称为缩小增量法，希尔排序的基本思想是：先选定一个整数，把待排序文件中所有记录分成若干个组，所有距离为“gap”的记录分在同一组内，并对每一个组内的记录进行排序。然后，取，重复上述分组和排序工作。当“gap”（间隔）==1，所有记录在统一组内排好序。
1.先进行预排序，使数组接近有序
2.直接插入排序
预排序：分组排，间隔为 gap 是一组，假设 gap ==3;
9 8 7 6 5 4 3 2 1 0,如果将这组数据升序排序，使用直接插入排序，算法的复杂度就是 O(N^2);
每个 gap 间隔的小分组都再进行插入排序。
优点：大数，小数更快的到达两端，当gap等于1时，就是直接插入排序，这时候时间复杂度就是大大降低。
2.2 程序实现：
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> //希尔排序 void ShellSort(int* a, int n)//升序 { int gap = n; while (gap > 1)//当gap等于1时，就是直接插入排序 { gap = gap / 2; //把间隔为gap的多组数据同时排序 for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; while (end>=0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } a[end + gap] = tmp; } } } //打印数据 Print(a, n); } int main() { int a[10] = { 9,8,7,6,5,4,3,2,1,0 }; //希尔排序 ShellSort(a, sizeof(a) / sizeof(a[0])); return 0; }
2.3 希尔排序的特征总结：
1.希尔排序是对直接插入排序的优化。
2.当gap>1时都是预排序，目的是让数组更接近于有序。当gap==1时，数组已经接近有序，这样就会很快。整体而言，可以达到优化的效果。
3.希尔排序的时间复杂度不好计算，需要根据数据进行推导，推导出来的的平均时间复杂度：O(N^1.3——N^2)。
4.稳定性：不稳定
至此插入排序的两种常用算法，直接插入排序和希尔排序博主已经分享完了，相信大家对这个插入排序的逻辑有了一定的理解，大家可以自己动手敲敲代码，感受一下。
本期收录于博主的专栏——排序算法，适用于编程初学者，感兴趣的朋友们可以订阅，查看其它“常见排序”。排序算法_保护小周ღ的博客-CSDN博客
感谢每一个观看本篇文章的朋友，更多精彩敬请期待：保护小周ღ *★,°*:.☆(￣▽￣)/$:*.°★*
遇见了你，所有的星星都落在了我的头上……
