【C/C++实现】直接插入排序（图例--超详细解析，小白一看就会！）
目录
一、前言
二、排序的概念及其分类
📒排序的概念
📒排序的分类
三、直接插入排序
🥝 基本思想
🍇 具体步骤
🍍代码分析与详解
①写出单趟的的插入过程
②利用循环控制每一趟插入排序
③完整的图例和代码演示
🍎 C/C++ 代码实现
⚡C语言代码实现
⚡C++ 代码实现（STL）
⚡C++ 代码实现（类模拟）
🍋时间复杂度分析
四、共勉
一、前言
排序是我们数据结构学习中很重要的章节，我们在生活中买东西都会挑选更好的，点外卖会选评分高的等等，这些都需要用到排序。并且在找工作的面试当中排序算法是会经常拿出来考的。那么接下来我们将会带大家一起学习常见的排序算法。 本次博客先从----直接插入排序算法讲起
二、排序的概念及其分类
📒排序的概念
⭐排序：所谓排序，就是使一串数据，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
⭐稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次 序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排 序算法是稳定的；否则称为不稳定的。
⭐内部排序：数据元素全部放在内存中的排序。
⭐外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
📒排序的分类
三、直接插入排序
🥝 基本思想
相信大家都玩过扑克牌吧，那么如何进行扑克牌的排序呢？
- 举个例子，比如我手中有红桃 6，7，9，10 这 4 张牌，已经处于升序排列：
- 时候，我又抓到一张红桃 8，如何让手中的 5 张牌重新变成升序呢？
- 最简单的方式，就是在已经有序的 4 张牌中找到红桃 8 应该插入的位置，也就是 7 和 9 之间，把红桃 8 插进去：
就像玩牌一样，有一种排序算法也采用了类似的思想：维护一个有序区，把元素一个个插入有序区的适当位置，直到所有元素都有序为止。
这样的排序算法，被称为直接插入排序。
🍇 具体步骤
直接插入排序是一种简单的插入排序法，其基本思想是：
- 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。
- 在待排序的元素中，假设前 n-1 个元素已有序，现将第 n 个元素插入到前面已经排好的序列中，使得前 n 个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
【核心思路】：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列
🍍代码分析与详解
对直接插入排序有了一个基本的了解以后，我们需要将这个思想去转化为代码
- 很多同学一开始刚有点思路就开始写代码，甚至什么都不想直接开始写，然后运行报错一大堆，各种数组访问越界、边界问题没有考虑、代码逻辑混乱。这其实是写程序的一个大忌，我们应该逐步分析，从简单到复杂、从单趟的排序到整体的排序去过渡
①写出单趟的的插入过程
- 首先对于单趟的逻辑，因为是要将一个数插入到一个有序区间中去，不妨设这个区间的最后一个位置为【end】，那这个待插入数据的位置就是【end + 1】，我们要将这个待插入的数据保存起来，因为在比较的过程中可能会造成数据的后移，那这个数就会被覆盖了
- 接着将待插入的数据与有序区间的最后一个数进行比较，因为默认选择排升序，所以是要将小的数据放到前面，所以若是这个待插入数据比 a[end] 要小，那 a[end] 便进行一个后移，但是呢，随着数据的不断增大，有序区也会越来越大，此时待插入数据就不只是和有序区的最后一个数据做比较了，需要和前面的所有数进行一个比较，那么我们就要将这段逻辑放在一个循环里。这个循环什么时候结束呢？就是当这个【end
- 若是在中途比较的过程中发现有比待插入数据还要小或者相等的数，就停止比较，跳出这个循环。因为随着有序区间中数的后移，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)
{
if (tmp
②利用循环控制每一趟插入排序
- 这一块我们只需要将单趟的插入过程放在一个循环中即可，逐渐扩大这个有序区，因此【end】即为每次递增的变量i。
- 这里要注意的一点是❗循环的结束条件i
for (int i = 0; i
③完整的图例和代码演示
接下来演示一下直接插入排序在数组中的具体实现步骤。
- 给定一组无序数组如下：
- 我们把首元素 6 作为有序区，此时有序区只有这一个元素：
- 第一轮，让元素 9 和有序区的元素依次比较，9 > 6，所以元素 9 和元素 6 无需交换。此时有序区的元素增加到两个：
- 第二轮，让元素 7 和有序区的元素依次比较，7
- 7 > 6，所以把元素 7 和元素 6 无需交换。此时有序区的元素增加到三个：
- 第三轮，让元素 4 和有序区的元素依次比较，4
- 4
- 4
- 此时有序区的元素增加到四个：
- 以此类推，插入排序一共会进行（数组长度-1）轮，每一轮的结果如下：
代码
/*直接插入排序*/ void InsertSort(int* a, int n) { //不可以= 0) { if (tmp🍎 C/C++ 代码实现
⚡C语言代码实现
#include #include // 插入排序 void InsertSort(int* a, int n) { // [0,end]有序，把end+1位置的插入到前序 // 控制 [0,end+1]有序 for (int i = 0; i = 0) { // 升序 if (temp \n"); for (int i = 0; i
⚡C++ 代码实现（STL）
#include #include #include using namespace std; vector& Insertsort(vector& nums, int len) { for (int i = 0; i = 0) { // 升序 if (temp \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
- 以此类推，插入排序一共会进行（数组长度-1）轮，每一轮的结果如下：
- 此时有序区的元素增加到四个：
- 4
- 4
- 第三轮，让元素 4 和有序区的元素依次比较，4
- 7 > 6，所以把元素 7 和元素 6 无需交换。此时有序区的元素增加到三个：
- 第二轮，让元素 7 和有序区的元素依次比较，7
- 第一轮，让元素 9 和有序区的元素依次比较，9 > 6，所以元素 9 和元素 6 无需交换。此时有序区的元素增加到两个：
- 我们把首元素 6 作为有序区，此时有序区只有这一个元素：
- 给定一组无序数组如下：
- 此时发现 end = 0)
{
if (tmp
- 此时发现 2 大于 1，所以将 2 向后移动，之后end 指针向前移动
- 此时发现 4 大于 1，所以将 4 向后移动，之后end 指针向前移动
- 此时发现 6 大于 1，所以将 6 向后移动，之后end 指针向前移动
- 此时发现 7 大于 1，所以将 7 向后移动，之后end 指针向前移动
- 此时发现 8 大于 1 ，所以将 8 向后移动，之后 end 指针向前移动
- 根据数组我们可以发现有序区域为 【2，4，6，7，8】 ，需要插入的数据为 【1】
- 很多同学一开始刚有点思路就开始写代码，甚至什么都不想直接开始写，然后运行报错一大堆，各种数组访问越界、边界问题没有考虑、代码逻辑混乱。这其实是写程序的一个大忌，我们应该逐步分析，从简单到复杂、从单趟的排序到整体的排序去过渡
- 最简单的方式，就是在已经有序的 4 张牌中找到红桃 8 应该插入的位置，也就是 7 和 9 之间，把红桃 8 插进去：
- 时候，我又抓到一张红桃 8，如何让手中的 5 张牌重新变成升序呢？
