【C/C++实现】直接插入排序（图例--超具体剖析，小白一看就会！）

【导语】数据结构排序算法的入门教程：先讲清排序与稳定性的概念（相同关键字排序后相对次序不变即为稳定）、内部排序与外部排序的分类，再用扑克牌插牌类比讲解直接插入排序的基本思想与单趟插入过程，随后用循环控制每一趟插入，给出 C 语言、C++ STL 与类封装三种完整实现并配完整图例，最后分析时间复杂度，图解细致，适合算法初学者与准备面试的读者。

---

目次
一、前言
二、排序的概念及其分类 
📒排序的概念 
📒排序的分类 
 三、直接插入排序
 🥝 根本头脑
 🍇 具体步调
 🍍代码分析与详解
①写出单趟的的插入过程 
 ②使用循环控制每一趟插入排序
③完备的图例和代码演示 
🍎 C/C++ 代码实现
⚡C语言代码实现 
⚡C++ 代码实现（STL）
⚡C++ 代码实现（类模仿）
 🍋时间复杂度分析
 四、共勉

---

一、前言

           排序是我们数据布局学习中很紧张的章节，我们在生存中买东西都会挑选更好的，点外卖会选评分高的等等，这些都必要用到排序。而且在找工作的口试当中排序算法是会经常拿出来考的。那么接下来我们将会带各人一起学习常见的排序算法。 本次博客先从----直接插入排序算法讲起
  二、排序的概念及其分类 

📒排序的概念 

⭐排序：所谓排序，就是使一串数据，按照此中的某个或某些关键字的巨细，递增或递减的分列起来的使用。

⭐稳固性：假定在待排序的记录序列中，存在多个具有雷同的关键字的记录，若颠末排序，这些记录的相对次 序保持稳定，即在原序列中，r = r[j]，且 r 在 r[j] 之前，而在排序后的序列中，r 仍在 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 < 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], 完成排序
  

 代码展示

1. int end;
2. int tmp = a[end + 1];                //将end后的位置先行保存起来
3. while (end >= 0)
4. {
5.         if (tmp < a[end])
6.         {
7.                 a[end + 1] = a[end];                //比待插值来得大的均往后移动
8.                 end--;                //end前移
9.         }
10.         else
11.         {
12.                 break;                //若是发现有相同的或者小于带插值的元素，则停下，跳出循环
13.         }
14. }
15. 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] ，那么这个位置就会出现一个随机值，以是各人在写这种循环的边界条件时一定提前做好分析✍，在运行之前保证心田胸中有数
  

1. for (int i = 0; i < n - 1; ++i)
2. {
3.         int end = i;
4.         //单趟插入逻辑...
5. }
6.        

复制代码

③完备的图例和代码演示 

    接下来演示一下直接插入排序在数组中的具体实现步调。
  

•  给定一组无序数组如下：
  

•  我们把首元素 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）轮，每一轮的效果如下：
  

代码 

1. /*直接插入排序*/
2. void InsertSort(int* a, int n)
3. {
4.                                                 //不可以< n，否则最后的位置落在n-1，tmp访问end[n]会造成越界
5.         for (int i = 0; i < n - 1; ++i)
6.         {
7.                 int end = i;
8.                 int tmp = a[end + 1];                //将end后的位置先行保存起来
9.                 while (end >= 0)
10.                 {
11.                         if (tmp < a[end])
12.                         {
13.                                 a[end + 1] = a[end];                //比待插值来得大的均往后移动
14.                                 end--;                //end前移
15.                         }
16.                         else
17.                         {
18.                                 break;                //若是发现有相同的或者小于带插值的元素，则停下，跳出循环
19.                         }
20.                 }
21.                 a[end + 1] = tmp;                //将end + 1的位置放入保存的tmp值
22.         }
24. }

复制代码

🍎 C/C++ 代码实现

⚡C语言代码实现 

1. #include <stdio.h>
2. #include <stdlib.h>
4. // 插入排序
5. void InsertSort(int* a, int n)
6. {
7.         // [0,end]有序，把end+1位置的插入到前序
8.         // 控制 [0,end+1]有序
9.         for (int i = 0; i < n - 1; i++)
10.         {
11.                 int end = i;
12.                 // 把 end 的后一个往前插入
13.                 int temp = a[end + 1];
14.                 while (end >= 0)
15.                 {
16.                         // 升序
17.                         if (temp < a[end])
18.                         {
19.                                 // 向后挪动
20.                                 a[end + 1] = a[end];
21.                         }
22.                         else
23.                         {
24.                                 break;
25.                         }
26.                         end--;
27.                 }
28.                 a[end + 1] = temp;
29.         }
30.         for (int i = 0; i < n; i++)
31.         {
32.                 printf("%d ", a[i]);
33.         }
34. }
36. int main()
37. {
38.         int a[100];
39.         int sum;
40.         int j = 0;
41.         printf("请输入你要排序的数据 以-1结束：> \n");
42.         for (int i = 0; i < 100; i++)
43.         {
44.                 scanf("%d", &sum);
45.                 if (sum == -1)
46.                 {
47.                         break;
48.                 }
49.                 a[j++] = sum;
50.         }
51.         InsertSort(a, j);
52.         return 0;
54. }

复制代码

⚡C++ 代码实现（STL）

1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. using namespace std;
6. vector<int>& Insertsort(vector<int>& nums, int len)
7. {
8.         for (int i = 0; i < len - 1; i++)
9.         {
10.                 int end = i;
11.                 int temp = nums[end + 1];
12.                 while (end >= 0)
13.                 {
14.                         // 升序
15.                         if (temp < nums[end])
16.                         {
17.                                 nums[end + 1] = nums[end];
18.                         }
19.                         else
20.                         {
21.                                 break;
22.                         }
23.                         end--;
24.                 }
25.                 nums[end + 1] = temp;
26.         }
27.         return nums;
28. }
30. int main()
31. {
32.         vector<int> v;
33.         printf("请输入你要排序的数据 以-1结束：> \n");
34.         while (1)
35.         {
36.                 int sum;
37.                 cin >> sum;
38.                 if (sum == -1)
39.                 {
40.                         break;
41.                 }
42.                 v.push_back(sum);
43.         }
44.         int len = v.size();
45.         v = Insertsort(v, len);
46.         for (auto ch: v)
47.         {
48.                 cout << ch << " ";
49.         }
50.         cout << endl;
51.         return 0;
52. }

复制代码

⚡C++ 代码实现（类模仿）

1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. using namespace std;
6. class Sort
7. {
8. public:
9.         // 构造函数  --- 有参构造
10.         Sort(int l)
11.                 :length(l)
12.         {
13.                 // 为数组开空间
14.                 array = new int[length];
15.         }
17.         // 构建数组的元素
18.         void build()
19.         {
20.                 cout << "请输入要排序的元素：" << endl;
21.                 for (int i = 0; i < length; i++)
22.                 {
23.                         int data;
24.                         cin >> data;
25.                         array[i] = data;
26.                 }
27.         }
29.         // 直接插入排序
30.         void InsertSort()
31.         {
32.                 for (int i = 0; i < length - 1; i++)
33.                 {
34.                         int end = i;
35.                         int temp = array[end + 1];
36.                         while (end >= 0)
37.                         {
38.                                 //升序
39.                                 if (array[end] > temp)
40.                                 {
41.                                         array[end + 1] = array[end];
42.                                 }
43.                                 else
44.                                 {
45.                                         break;
46.                                 }
47.                                 end--;
48.                         }
49.                         array[end + 1] = temp;
50.                 }
51.         }
53.         // 输出数组
54.         void Display()
55.         {
56.                 cout << "输出最终的排序结果： " << endl;
57.                 for (int i = 0; i < length; i++)
58.                 {
59.                         cout << array[i] << " ";
60.                 }
61.                 cout << endl;
62.         }
64. private:
65.         int* array;  //  数组首地址，尚未申请空间
66.         int length;  //  数组长度
67. };
69. int main()
70. {
71.         int length;
72.         cout << "请输入要排序元素的个数： " << endl;
74.         cin >> length;
75.         Sort s(length);
76.         s.build();
77.         s.InsertSort();
78.         s.Display();
79.         return 0;
80. }

复制代码

 🍋时间复杂度分析

   【时间复杂度】：O(N2)
【空间复杂度】：O(1)
  

• 看了代码之后我们再来看看其复杂度，起首是对于时间复杂度，这块看的是这个排序算法执行的次数，那对于直接插入排序这一块来说，取决于数据数据的分步，假想如果一些随机的数字，然后每次取到的tmp值可能就必要插入到中心、前面、末了三种情况👇
  

• 【最好的】是每一趟的内部比力都不必要移动数据，只必要遍历一下这个数组即可，然后把待插入的数放在末了即可。其时间复杂度就是O(N)；
  
• 【中心的】就是数据必要后移一般，其时间复杂度就是O(N/2)即O(N)； 
  
• 【最坏的】是必要插入到最前面的情况，由于对于tmp前面的每一个数字都必要向后挪动一位，也就意味着tmp要和这个数组的全部数字举行一个比力，然后又有N个数必要举行插入，此时时间复杂度就是O(N2)； 
  
• 对于空间复杂度盘算的额外的空间，在这里我们只是定义了一些变量，并没有去申额外的空间，因此空间复杂度为O(1)
  

 四、共勉

 以下就是我对 直接插入排序 的明白，假如有不懂和发现问题标小搭档，请在批评区说出来哦，同时我还会继续更新对 希尔排序 的明白，请连续关注我哦！！！