【C/C++实现】直接插入排序（图例--超详细解析，小白一看就会！）
创作时间:
作者:
@小白创作中心
【C/C++实现】直接插入排序（图例--超详细解析，小白一看就会！）
引用
CSDN
1.
https://blog.csdn.net/weixin_45031801/article/details/137880015
一、前言
排序是数据结构学习中很重要的章节。在日常生活中，无论是买东西还是点外卖，我们都会进行某种程度的排序。在找工作面试时，排序算法也是经常被考察的内容。接下来，我们将一起学习常见的排序算法，本次先从直接插入排序算法讲起。
二、排序的概念及其分类
排序的概念
排序是指使一串数据按照其中的某个或某些关键字的大小，递增或递减地排列起来的操作。
排序的稳定性
稳定性是指在待排序的记录序列中，存在多个具有相同的关键字的记录。如果经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序与外部排序
- 内部排序：数据元素全部放在内存中的排序。
- 外部排序：数据元素太多不能同时放在内存中，需要在内外存之间移动数据的排序。
三、直接插入排序
基本思想
直接插入排序的思想类似于玩扑克牌时的排序方式。假设我们手中有红桃6、7、9、10这4张牌，已经处于升序排列。当我们又抓到一张红桃8时，需要将其插入到合适的位置，使得手中的5张牌重新变成升序。这种排序算法维护一个有序区，将元素一个个插入有序区的适当位置，直到所有元素都有序为止。
具体步骤
直接插入排序的基本思想是：将待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
代码分析与详解
对直接插入排序有了一个基本的了解以后，我们需要将这个思想转化为代码。
①写出单趟的插入过程
- 首先对于单趟的逻辑，因为是要将一个数插入到一个有序区间中去，不妨设这个区间的最后一个位置为【end】，那这个待插入数据的位置就是【end + 1】，我们要将这个待插入的数据保存起来，因为在比较的过程中可能会造成数据的后移，那这个数就会被覆盖了
- 接着将待插入的数据与有序区间的最后一个数进行比较，因为默认选择排升序，所以是要将小的数据放到前面，所以若是这个待插入数据比a[end]要小，那a[end]便进行一个后移，但是呢，随着数据的不断增大，有序区也会越来越大，此时待插入数据就不只是和有序区的最后一个数据做比较了，需要和前面的所有数进行一个比较，那么我们就要将这段逻辑放在一个循环里。这个循环什么时候结束呢？就是当这个【end < 0】为止
- 若是在中途比较的过程中发现有比待插入数据还要小或者相等的数，就停止比较，跳出这个循环。因为随着有序区间中数的后移，end后一定会空出一个位置，此时呢执行
a[end + 1] = tmp;
就可以将这个待插入数据完整地放入有序区中并且使这个有序区依旧保持有序
根据上面的解析我们来用图例分析一下，单躺插入的过程，用例数组a = [2,4,6,7,8,1] ，此时需要排一个升序。
- 根据数组我们可以发现有序区域为【2，4，6，7，8】，需要插入的数据为【1】
- 此时发现 8 大于 1，所以将 8 向后移动，之后end指针向前移动
- 此时发现7 大于 1，所以将 7 向后移动，之后end指针向前移动
- 此时发现 6 大于 1，所以将 6 向后移动，之后end指针向前移动
- 此时发现 4 大于 1，所以将 4 向后移动，之后end指针向前移动
- 此时发现 2 大于 1，所以将 2 向后移动，之后end指针向前移动
- 此时发现end < 0跳出循环，temp = a[end + 1], 完成排序
代码展示
int end;
int tmp = a[end + 1]; //将end后的位置先行保存起来
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end]; //比待插值来得大的均往后移动
end--; //end前移
}
else
{
break; //若是发现有相同的或者小于带插值的元素，则停下，跳出循环
}
}
a[end + 1] = tmp; //将end + 1的位置放入保存的tmp值
②利用循环控制每一趟插入排序
- 这一块我们只需要将单趟的插入过程放在一个循环中即可，逐渐扩大这个有序区，因此【end】即为每次递增的变量i。
- 这里要注意的一点是❗循环的结束条件i < n - 1❗，这里不可以写成i < n，若是写成这样那么【i】最后落的位置就是【n - 1】。此时end获取到这个位置后去保存tmp的值时就会造成造成数组的越界访问 a[n - 1 + 1] = a[n]，那么这个位置就会出现一个随机值，所以大家在写这种循环的边界条件时一定提前做好分析✍，在运行之前保证心里胸有成竹
for (int i = 0; i < n - 1; ++i)
{
int end = i;
//单趟插入逻辑...
}
③完整的图例和代码演示
接下来演示一下直接插入排序在数组中的具体实现步骤。
- 给定一组无序数组如下：
- 我们把首元素6作为有序区，此时有序区只有这一个元素：
- 第一轮，让元素9和有序区的元素依次比较，9 > 6，所以元素9和元素6无需交换。此时有序区的元素增加到两个：
- 第二轮，让元素7和有序区的元素依次比较，7 < 9，所以把元素7和元素9进行交换：
- 7 > 6，所以把元素7和元素6无需交换。此时有序区的元素增加到三个：
- 第三轮，让元素4和有序区的元素依次比较，4 < 9，所以把元素4和元素9进行交换：
- 4 < 7，所以把元素4和元素7进行交换：
- 4 < 6，所以把元素4和元素6进行交换：
- 此时有序区的元素增加到四个：
- 以此类推，插入排序一共会进行（数组长度-1）轮，每一轮的结果如下：
代码
/*直接插入排序*/
void InsertSort(int* a, int n)
{
//不可以< n，否则最后的位置落在n-1，tmp访问end[n]会造成越界
for (int i = 0; i < n - 1; ++i)
{
int end = i;
int tmp = a[end + 1]; //将end后的位置先行保存起来
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end]; //比待插值来得大的均往后移动
end--; //end前移
}
else
{
break; //若是发现有相同的或者小于带插值的元素，则停下，跳出循环
}
}
a[end + 1] = tmp; //将end + 1的位置放入保存的tmp值
}
}
四、C/C++代码实现
C语言代码实现
#include <stdio.h>
#include <stdlib.h>
// 插入排序
void InsertSort(int* a, int n)
{
// [0,end]有序，把end+1位置的插入到前序
// 控制 [0,end+1]有序
for (int i = 0; i < n - 1; i++)
{
int end = i;
// 把 end 的后一个往前插入
int temp = a[end + 1];
while (end >= 0)
{
// 升序
if (temp < a[end])
{
// 向后挪动
a[end + 1] = a[end];
}
else
{
break;
}
end--;
}
a[end + 1] = temp;
}
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
}
int main()
{
int a[100];
int sum;
int j = 0;
printf("请输入你要排序的数据 以-1结束：> \n");
for (int i = 0; i < 100; i++)
{
scanf("%d", &sum);
if (sum == -1)
{
break;
}
a[j++] = sum;
}
InsertSort(a, j);
return 0;
}
C++代码实现（STL）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int>& Insertsort(vector<int>& nums, int len)
{
for (int i = 0; i < len - 1; i++)
{
int end = i;
int temp = nums[end + 1];
while (end >= 0)
{
// 升序
if (temp < nums[end])
{
nums[end + 1] = nums[end];
}
else
{
break;
}
end--;
}
nums[end + 1] = temp;
}
return nums;
}
int main()
{
vector<int> v;
printf("请输入你要排序的数据 以-1结束：> \n");
while (1)
{
int sum;
cin >> sum;
if (sum == -1)
{
break;
}
v.push_back(sum);
}
int len = v.size();
v = Insertsort(v, len);
for (auto ch: v)
{
cout << ch << " ";
}
cout << endl;
return 0;
}
C++代码实现（类模拟）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Sort
{
public:
// 构造函数 --- 有参构造
Sort(int l)
:length(l)
{
// 为数组开空间
array = new int[length];
}
// 构建数组的元素
void build()
{
cout << "请输入要排序的元素：" << endl;
for (int i = 0; i < length; i++)
{
int data;
cin >> data;
array[i] = data;
}
}
// 直接插入排序
void InsertSort()
{
for (int i = 0; i < length - 1; i++)
{
int end = i;
int temp = array[end + 1];
while (end >= 0)
{
//升序
if (array[end] > temp)
{
array[end + 1] = array[end];
}
else
{
break;
}
end--;
}
array[end + 1] = temp;
}
}
// 输出数组
void Display()
{
cout << "输出最终的排序结果： " << endl;
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
cout << endl;
}
private:
int* array; // 数组首地址，尚未申请空间
int length; // 数组长度
};
int main()
{
int length;
cout << "请输入要排序元素的个数： " << endl;
cin >> length;
Sort s(length);
s.build();
s.InsertSort();
s.Display();
return 0;
}
五、时间复杂度分析
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
看了代码之后我们再来看看其复杂度，首先是对于时间复杂度，这块看的是这个排序算法执行的次数，那对于直接插入排序这一块来说，取决于数据数据的分步，设想若是一些随机的数字，然后每次取到的tmp值可能就需要插入到中间、前面、最后三种情况。
- 最好的情况是每一趟的内部比较都不需要移动数据，只需要遍历一下这个数组即可，然后把待插入的数放在最后即可。那时间复杂度就是O(N)；
- 中间的情况是数据需要后移一般，那时间复杂度就是O(N/2)即O(N)；
- 最坏的情况是需要插入到最前面的情况，因为对于
tmp前面的每一个数字都需要向后挪动一位
，也就意味着tmp要和这个数组的所有数字进行一个比较，然后又有N个数需要进行插入，此时时间复杂度就是O(N^2)； - 对于空间复杂度计算的额外的空间，在这里我们只是定义了一些变量，并没有去申额外的空间，因此空间复杂度为O(1)
热门推荐
3.14圆周率日：如何理解无理数和有理数
如何让 30 平米具备五脏俱全功能？这套房装修给你答案！
长龙航空开通西安直飞槟城航线，助力两地旅游文化交流
什么是阻焊桥？一文讲透PCB板阻焊桥如何设计
艾灸一天可以做几次？一次多长时间？
HDMI技术详解：从1.4到2.1版本的演变及eARC/ARC功能解析
原酿黄酒制作工艺详解：从原料到陈酿的全过程
大体育观下的体育跨学科教学
辛亥革命失败证明了什么 说明了什么
猪头肉烹饪宝典：一道诱人美食的秘诀与攻略
孕期体重管理指南：不同阶段的标准与测量方法
前海泰康医院陈旻湖：引领我国炎症性肠病治疗走向国际前沿的消化病学巨擘
河州黄酒 传承的酿造技艺密码
公孙大娘：大唐第一舞人，以“舞剑”成就三圣
干细胞外泌体雾化！60分钟内到达心脏，帮助心肌梗死后心肌重塑
维护彩礼传统，彰显男方迎娶诚意，并为新婚家庭提供启动资金
古诗进入英语世界，不仅仅是翻译那么简单
Excel中自动提取行号和列号的多种方法
家庭电器使用中的防感应电措施
走进“大圣故里 西游胜境”，重新发现神奇浪漫之都连云港
凉性水果与热性水果：功效与食用指南
乙流超过48小时吃奥司他韦有用吗
女人，要搞雌竞，更要搞雄竞，这才是真正的高段位
绿色债券两类债权类型及其法律内涵
考研满分设置全解析：不同专业学位的考试分数分布
BCG矩阵详解：四象限评估产品定位与策略制定
体温38度如何处理：有效降温方法与注意事项
事业单位人员除名：开除与除名的区别及具体情形
动态修改nginx配置文件 nginx动态更新配置
如何保证Redis数据库数据一致性