哈喽大家好，我是保护小周ღ，本期为大家带来的是常见排序算法中的插入排序，主要有直接插入排序以及它的升级版——希尔排序，包您一看就会，快来试试吧~

---

目录

一、直接插入排序

1.1 基本思想

1.2 算法思想：

1.3 程序实现：

1.4 直接插入排序的总结：

二、希尔排序

2.1 算法思想：

2.2 程序实现：

2.3 希尔排序的特征总结：

---

一、直接插入排序

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博客

感谢每一个观看本篇文章的朋友，更多精彩敬请期待：保护小周ღ  *★,°*:.☆(￣▽￣)/$:*.°★* 

文章存在借鉴，如有侵权请联系修改删除！