【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)
热门推荐
加班费在劳动合同中的约定与履行
在设计项目中，如何与客户进行有效的沟通和需求理解
黑海东头望大秦：亚欧佛教、宗教交流与合作
解锁心理学硕士的力量，懂人性才能赢未来！
PNAS： 持续而稳定的湿润气候促进秦-西汉王朝社会经济繁荣
美国胡佛大坝争议：生态保护与人类发展的平衡术
十大好吃的简易营养便当 10种最受欢迎盒饭做法
揭秘金融市场的神秘龟甲，海龟交易法则深度解析
叶酸与 5-甲基四氢叶酸的生物学特征与应用，活性叶酸选择指南
酸模的功效与种植方法：一种兼具观赏、食用和药用价值的植物
如何将视频从PC传输到iPhone：iTunes及其他多种方法详解
iPhone和电脑之间互传文件的三种方法
酒后晨起口臭 背后的“神秘力量”
刮痧的正确使用方法
刮痧注意事项：这些关键点你必须知道
如何准确计算股息股利收益？这些收益计算方法有哪些应用场景？
揭开能量秘密：营养成分表中的能量如何计算？
如何通过股票的技术指标筛选优质股
哪吒当红！数字文创产业如何撬动商业地产新增长？
“汇资源+建平台+优服务” 成都高新区打造国内领先数字文创产业高地
陈皮怎么吃
开心消消乐全关卡攻略：从入门到精通的完整指南
军工箱：坚不可摧的装备守护者
微软与OpenAI合作关系演变的启示
骆宾王七岁写出成名作，长大后的他怎么样了？
天玑9300和骁龙8gen3哪个好？巅峰对决！一文告诉你谁是性能之王
茯砖茶的正确冲泡方法，这几点很重要！
肺结核复发几率大吗？三个关键因素及预防措施
Ubuntu的源管理详解
自己做好吃的鸡爪吧