常见排序算法之插入排序——直接插入排序、希尔排序

曾经终败给现在 2023-10-03 18:59 23阅读 0赞

### ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5L-d5oqk5bCP5ZGo4YOm_size_20_color_FFFFFF_t_70_g_se_x_16][] ###

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

![f89deef4fd5b408f8b4b1c0a50c0a9e9.png][]

![43b84f4183544cae90537b3f02f2e81c.png][]

--------------------

**目录**

一、直接插入排序

1.1 基本思想

1.2 算法思想：

1.3 程序实现：

1.4 直接插入排序的总结：

二、希尔排序

2.1 算法思想：

2.2 程序实现：

2.3 希尔排序的特征总结：

--------------------

### 一、直接插入排序 ###

#### 1.1 基本思想 ####

在生活当中，这种排序方式处处可见。

![de3b5e4e8ee64482a479ca8aefefbd07.jpeg][]

在玩扑克牌的时候我们就会采用插入排序的思想，当我们拿起第二张牌时，就会下意识的与第一张牌进行比较，如果比第一张牌小，我们则将牌插入至第一张牌的左边，反之就插入至右边（升序）。以图为例：我们拿起一张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\]……进行比较，找到插入位置，原来位置上的数据元素顺序往后移。

**用一组实例来观察一下是算法是怎么实现的的：**

![76ca5761d7e8405db967c9c0badf5334.png][]

--------------------

#### **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;
    }

![7e687016de5f4cbf8bedad699a45ff43.png][]

--------------------

#### **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);**

![d02a95f10bfe45e1baa79378b22c7f2e.png][]

**每个 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.稳定性：不稳定

--------------------

至此插入排序的两种常用算法，直接插入排序和希尔排序博主已经分享完了，相信大家对这个插入排序的逻辑有了一定的理解，大家可以自己动手敲敲代码，感受一下。

![40e36dfc27804c04afb4a9da45afda94.jpeg][]

本期收录于博主的专栏——排序算法，适用于编程初学者，感兴趣的朋友们可以订阅，查看其它“常见排序”。[排序算法\_保护小周ღ的博客-CSDN博客][-CSDN]

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

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

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5L-d5oqk5bCP5ZGo4YOm_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/8c9e9ec025db4ad1884bbc8f2cb13814.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5L-d5oqk5bCP5ZGo4YOm,size_20,color_FFFFFF,t_70,g_se,x_16
[f89deef4fd5b408f8b4b1c0a50c0a9e9.png]: https://img-blog.csdnimg.cn/f89deef4fd5b408f8b4b1c0a50c0a9e9.png
[43b84f4183544cae90537b3f02f2e81c.png]: https://img-blog.csdnimg.cn/43b84f4183544cae90537b3f02f2e81c.png
[de3b5e4e8ee64482a479ca8aefefbd07.jpeg]: https://img-blog.csdnimg.cn/de3b5e4e8ee64482a479ca8aefefbd07.jpeg
[76ca5761d7e8405db967c9c0badf5334.png]: https://img-blog.csdnimg.cn/76ca5761d7e8405db967c9c0badf5334.png
[7e687016de5f4cbf8bedad699a45ff43.png]: https://img-blog.csdnimg.cn/7e687016de5f4cbf8bedad699a45ff43.png
[d02a95f10bfe45e1baa79378b22c7f2e.png]: https://img-blog.csdnimg.cn/d02a95f10bfe45e1baa79378b22c7f2e.png
[40e36dfc27804c04afb4a9da45afda94.jpeg]: https://img-blog.csdnimg.cn/40e36dfc27804c04afb4a9da45afda94.jpeg
[-CSDN]: https://blog.csdn.net/weixin_67603503/category_11904303.html