—插入排序—
插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述
具体算法描述如下：
<1>.将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
<2>.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
代码实现
直接插入排序
void Insert_Sort(int a[], int n)
{
// 将第一个元素定为有序序列，从第二个元素开始遍历
for (int i = 1; i < n; ++i)
{
int key = a[i]; //从第二个元素开始移动
int j = i - 1; // 第一个元素的下标
while (j >= 0 && a[j] > key) // 若有序序列有元素值比大无序序列中大
{
a[j + 1] = a[j]; //比此元素大的所有有序元素往后移+1
j--;
}
a[j + 1] = key; // 将key放入合适位置
}
}
二分法插入排序
————————-有待填坑———————-
算法分析
平均情况：T(n) = O(n2)
最佳情况：输入数组按升序排列。T(n) = O(n)
最坏情况：输入数组按降序排列。T(n) = O(n2)
稳定性
稳定
若元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。故顺序不变
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 351134995@qq.com
