数据结构排序之插入排序
目录
[数据结构]排序之插入排序
1.基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为
止，得到一个新的有序序列
。
2直接插入排序：
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与
array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
注：基础不好的同学在写排序的时候建议先写单趟再写整体
单趟思想：将一个数字插入有序区间
// 插入排序---升序
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)//第一个数不需要排所以从1开始排
{
int end=i-1;
int temp=a[i];//将temp插入0~end区间中，保持有序
while (end >= 0)
{
if (temp < a[end])
{
a[end + 1] = a[end];//比end大那么把此时比temp大的数往后挪一位
end--;
}
else
{
break;//break出来以后有两种情况，第一种情况是数组元素比temp都大end一直减最后走到-1的位置；第二种情况是end走到一个比temp小的位置，不论是什么情况，end后面都为空并需要将temp插入进去
}
}
a[end + 1] = temp;
}
}break出来以后得两种情况
直接插入排序的特性总结：
元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：
O(N^2) 最坏情况
O(N^2) 最好情况
O(N)
空间复杂度：
O(1)
，它是一种稳定的排序算法
稳定性：稳定