[数据结构与算法]排序——插入排序

插入排序

思路：
将未排序的元素逐个插入到已排序的元素中，使其保持有序：

假设前i个元素有序（初始时默认第一个元素一定是有序的）
而后n-i个元素无序，那么从第n-i个元素开始逐个将无序元素插入到有序元素当中，并保持有序元素集仍保持有序，从而使有序元素集不断增加，使无序元素集不断减少，直到全部元素都保持有序为止。

#include <stdio.h>
#include <stdlib.h>

//插入排序
void InsertionSort(int array[],int length)//length为数组长度 
{
	int temp;
	int i,j,k;
	for(i=1;i<=length-1;i++)//将待排序的length-1个元素插入到有序的位置 
	{
		temp=array[i];
		for(j=i;j>0&&temp<array[j-1];j--)
		{
			array[j]=array[j-1];
		}
		array[j]=temp;
	}
 } 
 
 //主函数调用插入排序
 main()
 {
 	int i,j,k;
 	int array[6]={2,5,1,3,6,4};
 	InsertionSort(array,6);
 	for(i=0;i<6;i++)
 	{
 		printf("%d ",array[i]);
	 }
 	
  } 

时间复杂度分析：
外层必然有一个长度为n的循环
此循环中嵌套一个循环
嵌套的循环每次最小为0，最大为i即当前外层循环次数
最坏时间复杂度为：
1+2+3+…+n-1 = n(n-1)/2
T(n)=O(n^2)