目录
前言、
插入排序算法是必须掌握的一种基础算法，在一些比较出名的竞赛acm、蓝桥杯，可能会出现，而且作为简单题我们必须要拿下，所以我们要引起重视，下面让我们来深入了解插入排序算法。
一、什么是插入排序算法
插入排序（Insertion Sort）是一种简单直观的排序算法，其工作原理类似于我们平时整理扑克牌或手写数字时的排序方式。该算法的核心思想是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
二、插入排序的特点
时间复杂度
最坏情况：O(n^2)，当输入数组是反序的。
最好情况：O(n)，当输入数组已经是有序的。
平均情况：O(n^2)
空间复杂度
插入排序是原地排序算法，因此空间复杂度为O(1)。
稳定性
插入排序是稳定的排序算法，即不会改变相同元素的相对顺序。
适用性
插入排序适用于少量数据的排序，或者数据部分已经有序的情况。
通过插入排序算法，我们能够有效地对中小规模的数据集进行排序，同时保持代码的简洁和直观。对于大规模数据集，通常会选择更高效的排序算法，如快速排序或归并排序。
三、算法基本步骤
初始化：
1.从第一个元素开始，该元素可以认为已经被排序。
2.取出下一个元素，在已经排序的元素序列中从后向前扫描。
3.如果该元素（已排序）大于新元素，则将该元素移到下一位置。
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。
5.重复步骤2~5。
终止：
当所有元素都插入到已排序序列中，算法结束。
四、算法图解
五、c代码模板
#include <stdio.h>
// 插入排序函数
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将arr[i]插入到已排序的arr[0..i-1]中
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// 打印数组函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// 主函数
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
printf("未排序数组: ");
printArray(arr, n);
insertionSort(arr, n);
printf("已排序数组: ");
printArray(arr, n);
return 0;
}
六、经典例题
1.去掉最低工资和最高工资后的工资平均值
（帅哥们这个蓝色字体可以点进去看原题）
代码题解
class Solution {
void insertionSort(vector<int>&s){
for(int i=1;i<s.size();i++){
int x=s[i];
int j;
for(j=i-1;j>=0;j--){
if(x<s[j])s[j+1]=s[j];
else break;
}
s[j+1]=x;
}
}
public:
double average(vector<int>& salary) {
double sum=0.0000;
insertionSort(salary);
for(int i=1;i<salary.size()-1;i++){//去掉排序后第一个元素和最后一个元素
sum+=salary[i];
}
return sum/(salary.size()-2);
}
};
2.删除某些元素后的数组均值
（帅哥们这个蓝色字体可以点进去看原题）
class Solution {
void insertionSort(vector<int>&a){
for(int i=1;i<a.size();i++){
int x=a[i];
int j;
for( j=i-1;j>=0;j--){
if(a[j]>x)a[j+1]=a[j];
else break;
}
a[j+1]=x;
}
}
public:
double trimMean(vector<int>& arr) {
insertionSort(arr);
double sum=0;
int cnt=0;
int n=arr.size();
for(int i=n/20;i<n-n/20;i++){//看提示，n是二十的倍数，也就是说n除以20(n*0.05),就是去除前5%和后5%
sum+=arr[i];
cnt++;
}
return sum/cnt;
}
};
3.学生分数的最小差值
（帅哥们这个蓝色字体可以点进去看原题）
class Solution {
void insertionSort(vector<int>&a){
for(int i=1;i<a.size();i++){
int x=a[i];
int j;
for(j=i-1;j>=0;j--){
if(a[j]>x)a[j+1]=a[j];
else break;
}
a[j+1]=x;
}
}
public:
int minimumDifference(vector<int>& nums, int k) {
insertionSort(nums);
int ret=1000001;//定义一个之来记录最小值，赋值为很大的数
for(int i=0;i+k-1<nums.size();i++){//i+k-1这个范围一定小于数组的长度，
int l=i;//最左边那个值就是最小的值
int r=l+k-1;//最右边那个值就是最大的值
ret=min(ret,nums[r]-nums[l]);//判断当前的差值是否比之前的小，如果小，最小值就变成这个差值，否则还是原来的，min这个函数是自带的。
}
return ret;
}
};
七、结语
学习算法是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油。
关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢
