直接插入排序算法，看这篇就够了

活动地址：CSDN21天学习挑战赛

前言：
✌ 作者简介：游坦之 ✌
 大学软件工程在读，希望学到真本领，经世致用 
 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步
 人生格言：成好人，行好事，做儒猿
 如果感觉博主的文章还不错的话，还请关注、点赞、收藏三连支持一下博主哦

• 什么是直接插入排序？
• 举个例子
• 代码
• 总结

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

对{5,2,8,7,9,4,3}进行直接插入排序

第一步，容器是空的，取出第一个元素5，放在容器的第一位。

第二步，取出第二位元素2，与有序容器里的元素依次排序，此时有序容器里只有一个元素5,2与5进行比较，2比5小，2放在5前面。

第三步，取出元素8，依次与有序容器里的元素进行比较。与2进行比较，大于2，继续往后进行比较，8还是大于5，所以放在5的后面。

第四步，取出元素7，依次与有序容器里的元素进行比较。和2进行比较，7>2，继续往后取出元素5进行比较,7>5，继续取出元素8进行比较。7<8，所以7放在元素8的前面。

第五步，取出元素9，依次与有序容器里的元素进行比较。和2进行比较，9>2，继续往后取出元素5进行比较，9>5，继续元素7进行比较，9>7，继续往后取出元素8，进行比较，9>8，所以9放在8的后面。

第六步，取出元素4，依次与有序容器里的元素进行比较，和2进行比较，4>2，继续往后取出元素5进行比较，4<5，所以4就放在5前面。

第七步，取出元素3，依次与有序容器里的元素进行比较，和2进行比较,3>2，继续取出元素4进行比较，此时3<4，所以把元素3放在元素4的前面。

#include 
using namespace std;
const int M = 10010;
int a[M];
int s[M];
int n;
int s_num = 0;//记载 
int main()
{
	cout<<"请输入有多少个数据"<>n;
	cout<<"请输入数据"<>a[i];
	}
	for(int i=0;i=j;k--)//后移的操作 
				{
					s[k+1] = s[k]; 
				}
				s_num++;
				flag = false;//代表置换了
				s[j] = a[i];
				break; 
			}
		}
		if(flag)//意味着这个数比s这个有序数组里面所有的元素的都大 
		{
			
			s[s_num++] = a[i];
		}
	}
	for(int i=0;i 
 
总结 
​ 由上面的栗子可以清晰的看出，直接插入排序需要两个容器，一是承载所有的集合，而是承载逐步扩充的有序集合。有序集合本是空集，随着每一步的扩充，集合的元素总数加1.也就是原集合有多少个元素，就需要进行多少步，即原有n个元素，就要进行n步排序。而每一步排序，最坏情况都需要遍历m次，这就意味着直接插入排序的时间复杂度即为O(n2)。但是从上面的代码来看，如果用到的是普通的数组，对于数组后移这样的操作，仍需要遍历z次，这就意味着时间复杂度变成了O（n3)。对此，我们可以用动态数组或者是链表进行优化。
 
​ 就比赛而言，每个比赛的时间限制大体在1s，计算量在10的8次方，对于O（n2）的时间复杂度而言，直接插入排序适合的计算量大约在10000左右，超过10000的数据不太适合用直接插入排序。则需要更高效的算法，或者需要更方便的容器。
 
​ 而对于容器而言，常见的有数组、链表、set、vector、map、queue、stack等等。
 
 
 
 
✨
     
      
       
        
         
          原创不易，还希望各位大佬支持一下
         
        
       
       
        textcolor{blue}{原创不易，还希望各位大佬支持一下}
       
      
     原创不易，还希望各位大佬支持一下 

  
     
      
       
        
         
          点赞，你的认可是我创作的动力！
         
        
       
       
        textcolor{green}{点赞，你的认可是我创作的动力！}
       
      
     点赞，你的认可是我创作的动力！ 

 ⭐️ 
     
      
       
        
         
          收藏，你的青睐是我努力的方向！
         
        
       
       
        textcolor{green}{收藏，你的青睐是我努力的方向！}
       
      
     收藏，你的青睐是我努力的方向！ 

 ✏️ 
     
      
       
        
         
          评论，你的意见是我进步的财富！
         
        
       
       
        textcolor{green}{评论，你的意见是我进步的财富！}
       
      
     评论，你的意见是我进步的财富！