排序相关算法--1.插入排序+冒泡排序回顾-2.插入排序

特点：有实践意义（例如后期快排的优化），适应性强，一般不会到时间复杂度最坏的情况。

1. 将第一个元素视为已经排好序的序列。
2. 取出下一个元素，在已经排好序的序列中从后往前比较，直到找到合适的位置插入。
3. 重复步骤2，直到所有元素都插入到合适的位置。

1. //插入排序
   #include<stdio.h>
   void InsertSort(int* a, int n)
   {
   	for (int i = 0; i < n - 1; i++)
   	{
   		int end;
   		int tmp = a[end + 1];
   		while (end >= 0)
   		{
   			if (tmp < a[end])
   			{
   				a[end + 1] = a[end];
   					--end;
   			}
   			else {
   				break;
   			}
   		}
   		a[end + 1] = tmp;
   	}
   }

上图一种特殊情况：此时不是break出来的而是一直进行--

所以不走else了,因此将最后一句放在外面无论是哪种情况都可以

单趟

排序：先理解单趟然后加上循环

整清楚边界。因为是从0开始访问的，所以只能访问到n-1;

因此在访问的时候只循环到n-2;,

i的最后一个值是n-2;所以是i<n-1;

计算插入排序的时间复杂度

时间复杂度计算最坏情况：逆序（就相当于一个等差数列）O(N^2)   N的平方。

最好：顺序 O(N)（只比一遍）

介于两者中间。