插入排序（直接插入排序）

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

接下来我们就要插入数据，即就要比较a[end]和tmp谁小，谁小谁放在前面（假设我们都是按照升序排）。前一个位置比较谁大谁小，

如果a[end]>tmp的话，那tmp就要往前挪，a[end]就要往后挪一个位置；即a[end+1]=a[end];此时不能直接让a[end]=tmp,这个时候end--，继续跟前一个位置比较谁大谁小

  if(a[end]>tmp)
  {
     a[end+1]=a[end];
     end--;
  }

接下来我们走else情况，即a[end]<=tmp,tmp都已经大于已经拍好的序列的最后一个位置了，那肯定比这个序列的所有数都大。这个时候我们只需要把tmp赋给end+1位置就好了，但是我们可以不在这个添加这个语句，我们直接用break跳出else,我们在等tmp一遍遍走完if条件，最后一次走玩else的时候在最后添加这个语句，当a[end]>tmp一次次让end--，指定end=0的时候a[end]还是大于tmp，end--=-1，那就证明tmp是最小的，那就可以在while循环后面加a[end+1]=tmp。让新的a[0]=tmp。

while (end >= 0)
{
	if (a[end] > tmp)
	{
		a[end + 1] = a[end];
		end--;
	}
	else
	{
		break;
	}

}
a[end + 1] = tmp;

走到这里，这就相当插入一个数走完了，那还有n-2个数还有插入（因为第一个数自动有序不用插入，一般从第二个数插入）。所以我们外面再套一层循环

for(i=0;i<n-1;i++)
{
   ....
}

为什么是i<n-1呢？因为i是从0开始，而我们是从a[1]开始插入数据的。

测试

#include<stdio.h>
int main()
{
	
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	int n = sizeof(a) / sizeof(a[0]);
	InsertSort(a, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

这个排序到这里也就写完了。

时间复杂度

这个排序的时间复杂度是多少呢？插入一个数，需要最坏情况下需要挪动多少次?肯定就是从end+1位置挪动到0位置，一共需要插入n-1个数，所以直接插入排序的时间复杂度是O（N^2）。